11.md

博弈型动态规划

• 一方先下（先手），在一定规则下依次出招，如果满足一定条件，则一方胜
• 博弈型动态规划在确定状态的时候，不考虑最后一步，先考虑第一步

博弈型动态规划的使用

1. 取石子问题

• 有一排 N 个石子，A 和 B 两人轮流取石子
• 每次一个人可以从左右边取 1 个或者 2 个石子
• 取走最后的石子的人获胜
• 问：先手A是否必胜，必胜返回true，否则返回false
• 如：N=5，A 先取 2 个，然后 B 怎么取，都是 A 赢
• 必胜态与必败态：只要下一步能走到必败的状态，那么这个人就必胜，如果下一步无论怎么走都是必胜，那么这个人就必败
• 如果取 1 个或者 2 个石子，能让剩下的局面先手必败，则当前先手必胜；如果无论怎么走，剩下的局面都是先手必胜，则当前先手必败
• 要求面对 N 个石子，是否先手胜，需要知道面对 N-1 和 N-2 个石子，是否先手胜，所以先手走一步后，剩下的局是一个子问题，规模更小
• 确定状态
  1. 状态：f[i]表示面对 i 个石子的时候，是否先手胜
• 转义方程
  1. f[i] = false === f[i-1] OR false===f[i-2] （有一个 false，先手赢，全是 true，先手输）
• 初始条件与边缘情况
  1. f[0] = false f[1]=f[2]=true
• 计算顺序
  1. f[0],...,f[n]

// 按照数学归纳法，num是3的倍数，先手输，否则先手败
// 普通方法
function firstWillWin(num) {
  if (num === 0) {
    return false;
  }
  if (num === 1) {
    return true;
  }
  var f = new Array(num + 1);
  f[0] = false;
  f[1] = true;
  for (var i = 2; i <= num; i++) {
    f[i] = !f[i - 1] || !f[i - 2];
  }
  return f[num];
}
var test = 3;
console.log(firstWillWin(test));
// false

// 滚动数组实现
function firstWillWin2(num) {
  if (num === 0) {
    return false;
  }
  if (num === 1) {
    return true;
  }
  var f = new Array(2);
  var old = false;
  var now = true;
  for (var i = 2; i <= num; i++) {
    var t = !now || !old;
    old = now;
    now = t;
  }
  return now;
}
var test = 3;
console.log(firstWillWin2(test));
// false