博弈型动态规划——硬币排成一条线

港控/mmm° 2022-10-27 06:29 166阅读 0赞

有 `n` 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。

请判定 **先手玩家** 必胜还是必败?

若必胜, 返回 `true`, 否则返回 `false`.

样例

**样例 1:**

输入: 1
    输出: true

**样例 2:**

输入: 4
    输出: true
    解释: 
    先手玩家第一轮拿走一个硬币, 此时还剩三个.
    这时无论后手玩家拿一个还是两个, 下一次先手玩家都可以把剩下的硬币拿完.

### 1、题目分析 ###

这是典型的博弈类型的动态规划题目

### 2、确定状态 ###

博弈类型的动态规划通常从第一部分析而不是最后一步。因为局面会变得越来越简单硬币的数量会越来越少。

当面对N个硬币的时候，先手第一步可以拿1个或者2个硬币。这样后手就面对N-1个硬币或者N-2个硬币。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

通过上面这个图可以看出，如果取1个或者两个硬币后，能够让剩下的局面先手必败，则当前先手必胜。

因此我们可以假设状态f\[i\]表示面对i个硬币的时候，是否是否先手f\[i\]为True或者False。

### 3、转移方程 ###

假设状态f\[i\]表示面对i个硬币的时候，是否是否先手f\[i\]为True或者False。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]

### 4、初始条件或者边界情况 ###

f\[0\]=False表示面对0个硬币，先手必败

f\[1\]=f\[2\]=True，表示面对1个或者2个硬币，先手必胜。

### 5、计算顺序 ###

从小到大。

答案就是f\[N\]=True则先手必胜，否则先手必败。

时间复杂度为O(N)，空间复杂度为O(N)

### 6、代码实现 ###

class Solution:
        """ @param n: An integer @return: A boolean which equals to true if the first player will win """
        def firstWillWin(self, n):
            # write your code here
            if n==0:
                return False
            if n==1:
                return True
            else:
                dp=[False for i in range(n+1)]
                dp[1]=True
                for i in range(2,n+1):
                    if dp[i-1]==False or dp[i-2]==False:
                        dp[i]=True
            return dp[n]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/663b86ada7d24bdfa49a8a215b14eb0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]: /images/20221024/f568c0e27e414003a66044ffb286cffd.png