九章算法笔记D4-博弈型动态规划

字数统计905阅读时长7分阅读次数

@[toc]

D4 博弈型动态规划

Coins in a Line

Problems：

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

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

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

样例 :

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

确定状态：

博弈型动态规划通常从第一步 分析，而不是最后一步（因为局面越来越简单，硬币数越来越少）

知识点：

  1. 如果取1个或2个硬币后，能让剩下的局面先手必败，则当前先手必胜
  2. 如果不管怎么走，剩下的局面都是先手必胜，则当前先手必败
  3. 总之：
    • 必胜： 在当下的局面走出一步，让对手无路可逃
    • 必败： 自己无路可逃
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean firstWillWin(int n) {
  if (n == 0)
    return false;
  if (n == 1)
    return true;
  boolean[] f = new boolean[n + 1];
  int i;
  f[0] = false;
  f[1] = true;
  for (i = 2; i <= n; i++) {
    f[i] = (!f[i - 1]) || (!f[i - 2]);
  }
  /*可以证明, 当硬币数目是3的倍数的时候, 先手玩家必败, 否则他必胜.
      当硬币数目是3的倍数时, 每一轮先手者拿a个, 后手者拿3-a个即可, 后手必胜.
      若不是3的倍数, 先手者可以拿1或2个, 此时剩余硬币个数就变成了3的倍数
        */
  return f[n];
}

Coins in a Line III

Problem

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

Example

1
2
3
Given array A = [3,2,2], return true.
Given array A = [1,2,4], return true.
Given array A = [1,20,4], return false.

分析

设己方数字和是A，对手数字和是B，即目标是A>=B，由于记录两个变量的状态太复杂，所以还是把两个选手当成一个人，每次面对a[i…j]选最优解。这里dp[i][j]是当前选手对a[i…j]所选的coins与对手将要选的coins的最大差值。

初始条件：dp[i][i] = values[i]。因为只有1个coin，肯定是全选。

转移方程：f[i][j] = max{a[i] - f[i+1][j], a[j] - f[i][j-1]}

  1. f[i][j]：为一方先手在面对a[i...j]这些数字时，能得到的最大的与对手的数字差
  2. a[i] - f[i+1][j]：选择a[i]，对手采取最优策略时自己能得到的最大的与对手的数字差
  3. a[j] - f[i][j-1]：选择a[j]，对手采取最优策略时自己能得到的最大的与对手的数字差

计算顺序

f[0][0], f[1][1], f[2][2], …, f[n-1][n-1] //len = 0, 1 coin
f[0][1], …, f[n-2][n-1] //len = 1, 2 coins
…
f[0][n-1] //len = n - 1, n coins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution{
    public boolean firstWillWin(int[] A){
    	int n = A.length;
        int[][] f = new int[n][n];
        int i,j,len;
        for(i=0; i < n; i++)	f[i][i] = A[i];
        for(len = 2; len <= n; len++)
            for(i = 0; i <= n; i++){
            	j = i + len -1;
                f[i][j] = Math.max(A[i] - f[i+1][j],A[j] - f[i][j -1];
            }
		return f[0][n-1]>=0;
	}
}