最近一网友在网上发文称：华为把外包当日本人整，周一到周五每天八点半下班，周末不加班，说工时不够，工作不饱和，要上强度，工资是正编零头，要上正编强度。

外包本来就是靠人头挣钱的，干的越多他们就挣的越多，一年的项目恨不得3个月让你做完，所以基本上没有喘息的机会，如果有能力尽量不要去外包。

不过现在就业环境也不太好，以前看不上的外包现在要求也越来越高了，现在很多外包都要求至少本科学历了。就是因为人多，所以他们才会这么肆无忌惮要求你加班。

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

来看下今天的算法题，这题是LeetCode的第1510题：石子游戏 IV，难度是困难。

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走任意非零平方数个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

示例1：

输入：n = 4 输出：true 解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。

示例2：

输入：n = 7 输出：false 解释：当 Bob 采取最优策略时，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。

这题我们可以使用动态规划来解决，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];     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧 。