动态规划——博弈型

电玩女神 2023-06-30 02:20 24阅读 0赞

# 博弈型 #

--------------------

## 目录 ##

1.  概述
2.  硬币排成线

--------------------

### 1. 概述 ###

1.  博弈为两方游戏，一方先下，在一定的规则下依次出招，如果满足一定条件，则一方胜
2.  先手：先出招的一方。出招后，先手换人，新的先手面对一个新的局面

--------------------

### 2. 硬币排成线 ###

##### 1. 题目描述 #####

1.  有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。  
    请判定 先手玩家 必胜还是必败?
    
    例子：  
    输入：n=5  
    输出：true(先手取走2个硬币，剩下3个硬币，无论后手怎么拿，先手都可以取走最后一个硬币)

##### 2. 思路 #####

1.  确定状态  
    1. 博弈动态规划通常从第一步分析，而不是最后一步，因为局面越来越简单，硬币数越来越少  
    2. 面对N个石子，先手可以拿1个或者2个硬币，这样后手就面对N-1或N-2个石子。先手一定会选择让自己赢的一步  
    3. 如果取1个或2个硬币后，能让剩下的局面先手比败，则当前先手必胜  
    4. 如果不管怎么走，剩下的局面都是先手比胜，则当前先手必败
2.  转移方程  
    设 f\[i\] 表示面对i个硬币，是否先手必胜（f\[i\]=true/false）
3.  初始条件和边界情况  
    初始条件  
    f\[0\]=false，面对0个硬币，先手必败  
    f\[1\]=f\[2\]=true，面对1个或者2个硬币，先手比胜
4.  计算顺序  
    f\[0\], f\[1\], f\[2\],…f\[N\]

##### 3. 代码实现 #####

public boolean firstWillWin(int n) {
        
            if (n == 0) {
        
                return false;
            }
            if (n == 1) {
        
                return true;
            }
            boolean[] f = new boolean[n + 1];
            f[0] = false;
            f[1] = true;
            for (int i = 2; i <= n; i++) {
        
                f[i] = (!f[i - 1]) || (!f[i - 2]);
            }
            return f[n];
        }