九章算法笔记D4-博弈型动态规划
@[toc]
D4 博弈型动态规划
Coins in a Line
Problems:
有 n
个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币,直到没有硬币为止。拿到最后一枚硬币的人获胜。
请判定 先手玩家 必胜还是必败?
若必胜, 返回 true
, 否则返回 false
.
样例 :
1 | 输入: 4 |
确定状态:
博弈型动态规划通常从第一步 分析,而不是最后一步(因为局面越来越简单,硬币数越来越少)
知识点:
- 如果取1个或2个硬币后,能让剩下的局面先手必败,则当前先手必胜
- 如果不管怎么走,剩下的局面都是先手必胜,则当前先手必败
- 总之:
- 必胜: 在当下的局面走出一步,让对手无路可逃
- 必败: 自己无路可逃
1 | public boolean firstWillWin(int 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 | Given array A = [3,2,2], return true. |
分析
设己方数字和是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]}
f[i][j]
:为一方先手在面对a[i...j]
这些数字时,能得到的最大的与对手的数字差a[i] - f[i+1][j]
:选择a[i]
,对手采取最优策略时自己能得到的最大的与对手的数字差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 coinf[0][1]
, …, f[n-2][n-1]
//len = 1, 2 coins
…f[0][n-1]
//len = n - 1, n coins
1 | public class Solution{ |