最近一網(wǎng)友在網(wǎng)上發(fā)文稱：華為把外包當日本人整，周一到周五每天八點半下班，周末不加班，說工時不夠，工作不飽和，要上強度，工資是正編零頭，要上正編強度。

外包本來就是靠人頭掙錢的，干的越多他們就掙的越多，一年的項目恨不得3個月讓你做完，所以基本上沒有喘息的機會，如果有能力盡量不要去外包。

不過現(xiàn)在就業(yè)環(huán)境也不太好，以前看不上的外包現(xiàn)在要求也越來越高了，現(xiàn)在很多外包都要求至少本科學歷了。就是因為人多，所以他們才會這么肆無忌憚要求你加班。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第1510題：石子游戲 IV，難度是困難。

Alice 和 Bob 兩個人輪流玩一個游戲，Alice 先手。一開始，有 n 個石子堆在一起。每個人輪流操作，正在操作的玩家可以從石子堆里拿走任意非零平方數(shù)個石子。

如果石子堆里沒有石子了，則無法操作的玩家輸?shù)粲螒颉?/p>

給你正整數(shù) n ，且已知兩個人都采取最優(yōu)策略。如果 Alice 會贏得比賽，那么返回 True ，否則返回 False 。

示例1：

輸入：n = 4 輸出：true 解釋：n 已經(jīng)是一個平方數(shù)，Alice 可以一次全拿掉 4 個石子并贏得勝利（4 -> 0）。

示例2：

輸入：n = 7 輸出：false 解釋：當 Bob 采取最優(yōu)策略時，Alice 無法贏得比賽。 如果 Alice 一開始拿走 4 個石子， Bob 會拿走 1 個石子，然后 Alice 只能拿走 1 個石子，Bob 拿走最后一個石子并贏得勝利（7 -> 3 -> 2 -> 1 -> 0）。 如果 Alice 一開始拿走 1 個石子， Bob 會拿走 4 個石子，然后 Alice 只能拿走 1 個石子，Bob 拿走最后一個石子并贏得勝利（7 -> 6 -> 2 -> 1 -> 0）。

• 1 <= n <= 10^5

問題分析

這題說的是 A 和 B 兩個人玩游戲，每次每個人只能從石子中拿走任意非 0 的平方個石子，A 先拿，如果輪到誰，但沒有石子了，則誰輸。如果 A 贏則返回true，否則返回true。

這題我們可以使用動態(tài)規(guī)劃來解決，dp[i]=true表示有 i 個石子的時候 A 贏，dp[i]=false表示有 i 個石子的時候 A 輸。

對于 i 個石子，如果存在dp[i-j*j]為false，在開始的時候 A 只需要先拿 j*j 個石子，則 A 即可獲勝。因為 A 先拿 j*j ，剩下的 i-j*j 個是 B 開始拿，因為dp[i-j*j]返回的是 false ，所以 B 不可能獲勝。

JAVA：

public boolean winnerSquareGame(int n) {     boolean[] dp = new boolean[n + 1];     dp[1] = true;     for (int i = 1; i <= n; i++) {         boolean tmp = true;         // dp[i - j * j]只要有一個false，Alice就可以選擇j * j獲得勝利。         for (int j = 1; tmp && j * j <= i; j++)             tmp = dp[i - j * j];         dp[i] = !tmp;     }     return dp[n]; }

C++：

public:     bool winnerSquareGame(int n) {         vector
               
  dp(n + 1, false);         dp[1] = true;         for (int i = 1; i <= n; i++) {             bool tmp = true;             // dp[i - j * j]只要有一個false，Alice就可以選擇j * j獲得勝利。             for (int j = 1; tmp && j * j <= i; j++)                 tmp = dp[i - j * j];             dp[i] = !tmp;         }         return dp[n];     }
       

筆者簡介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧 。