博弈论与智力题合体的动态规划算法——尼姆游戏（Nim Game）

尼姆游戏是一道难度为简单的算法题。小编认为它的简单在于答案简单，但在不知道答案的前提下，小编认为可把它归类到动态规划中，小编之前的文章中也提过，动态规划的题目也可用递归的形式来解答。

那么，小编今天就带大家从递归开始，一点一点地分析这道博弈论与智力题合体算法题。不要先看最后的答案，没啥意思！！！

image-20220828110739455

递归分析

题目中表达的是轮到的人可以拿掉 1 - 3 块石头，并且拿到最后一块石头的人获胜，也就是说当轮到你拿时，剩下 1 - 3 块石头时，你就获胜了。同样地，你拿完 1 - 3 块石头后，并给对手剩下 1 - 3 块石头时，你就输掉游戏。

基于上文的表达，可得到递归的终止条件（以你为参考）：

• 轮到你时，没有可拿的石头（<=0），你输；
• 轮到你时，只有 1 - 3 三个数量的石头，你赢。

if n <= 0 {
  return false
} else if n < 4 {
  return true
}

那当石头数量大于 3 时，是怎样的呢？

• 假设你选择了 1 块石头，给对手留下了 1 - 3 块石头，你输；
• 同样，假设你拿掉 2 块或 3 块石头，给对手留下 1 - 3 块石头，你也是输。

结合上述终止条件，当递归参数被你减去 1 - 3 三种情况都返回的是 true 时说明是对手赢了。

func canWinNim(n int) bool {
	if n <= 0 {
		return false
	} else if n < 4 {
		return true
	}

	if canWinNim(n-1) && canWinNim(n-2) && canWinNim(n-3) {
		return false
	}

	return true
}

对于如何加缓存来减少重复计算的问题就由读者自己处理了，也可去查看小编以前的文章。

动态规划分析

从递归分析中可以知道，状态可以定义成一维数组【小编故意忽略掉的缓存】，且dp[i] 表达为当石头数量为 i 时，你是赢是输？

从递归的终止条件就有：

dp[0] = false
dp[1] = true
dp[2] = true
dp[3] = true

石头数量大于等于 4 时，都有 i-(1/2/3) 三种可能，只有当后手的这三种可能性都必胜时，i 才会必败。所以状态转移应是：

dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3]

因为 n 有边界问题需要被处理，所以：

func canWinNim(n int) bool {
	dp := make([]bool, n+4) // 兼容 n 不够 4 的情况
	dp[0], dp[1], dp[2], dp[3] = false, true, true, true
	for i:=4; i<=n; i++ {
		dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3]
	}

	return dp[n]
}

智力结论

首先可以把动态规划计算结果打印出来。可以发现，当 n 为 0 或者 为 4 的倍数时都输掉了游戏。

[false true true true false true true true false true true true false true false false false]

在不知道博弈论的情况，小编认为可以如下思考，因为要赢得比赛，那一定要让对手在最后一轮面对的石头数量是 4，即对手无论从 4 中拿掉 1 - 3 中哪个数量石头，自己都赢得比赛。于是先手可以通过调整所选石子数量，来维持「n % 4 != 0」直到最后回合。这与前文打印的结果是相符合的。所以本题的最终答案：

func canWinNim(n int) bool {
	return n % 4 != 0
}

扫码_搜索联合传播样式-标准色版