• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

1510. 石子游戏 IV

开发技术 开发技术 1个月前 (05-13) 11次浏览

难度 hard
Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。

一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

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

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

示例 1:

输入:n = 1
输出:true
解释:Alice 拿走 1 个石子并赢得胜利,因为 Bob 无法进行任何操作。
示例 2:

输入:n = 2
输出:false
解释:Alice 只能拿走 1 个石子,然后 Bob 拿走最后一个石子并赢得胜利(2 -> 1 -> 0)。
示例 3:

输入:n = 4
输出:true
解释:n 已经是一个平方数,Alice 可以一次全拿掉 4 个石子并赢得胜利(4 -> 0)。
示例 4:

输入: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)。
示例 5:

输入:n = 17
输出:false
解释:如果 Bob 采取最优策略,Alice 无法赢得胜利。

提示:

1 <= n <= 10^5

解题思路:这道题目和之前做过的一道题1690. 石子游戏 VII很像,采用动态规划的思路解决问题,难度是hard级别,看了题解之后感觉应该是medium偏上吧,感觉以后还是不要被标签影响到了做题心态,其实这道题是比较好解决的,比1690那道题目更好解决。首先定义dp[i]的状态为先手战况,如果true就是赢,false就是输,然后进行遍历,查找是否有k满足k*k <=i且dp[k]为false的情况,如果有,那就是在dp[k]这个状态,下先手的人是输的,因此只要保证当前操作是拿走k*k个石子,那状态转移到dp[k]那个状态了,对方必输,此时可以保证当前dp[i]的先手战况是赢,这时就break掉,跳出循环,如果k遍历完,没有发现这种对方必输的状态,那for循环退出后当前dp[i]的状态就是false,也就是此时状态下先手战况为输,也是正确的状态,直接进入下一个状态即可。

代码 t65 s90 java

class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] dp = new boolean[n+1];
        for(int i=1; i<=n; i++){
            for(int k=1; k*k<=i; k++){
                if(!dp[i-k*k]){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

参考资料
https://www.cnblogs.com/zhengxch/p/14691354.html
https://leetcode-cn.com/problems/stone-game-iv/solution/shi-zi-you-xi-iv-by-leetcode-solution/


程序员灯塔
转载请注明原文链接:1510. 石子游戏 IV
喜欢 (0)