给定一个整数栈,玩家轮流从栈顶移除1、2或3个数字。假设对手采取最佳策略,并且您先选择,我想到了以下递归方法:
int score(int n) {
if (n <= 0) return 0;
if (n <= 3) {
return sum(v[0..n-1]);
}
// maximize over picking 1, 2, or 3 + value after opponent picks optimally
return max(v[n-1] + min(score(n-2), score(n-3), score(n-4)),
v[n-1] + v[n-2] + min(score(n-3), score(n-4), score(n-5)),
v[n-1] + v[n-2] + v[n-3] + min(score(n-4), score(n-5), score(n-6)));
}
基本上,每个级别都会比较选择1、2或3后,你的对手选择1、2或3所得出的结果。
我在思考如何将其转换为DP解决方案,因为它显然是指数级的。我很困惑的是似乎有三个维度:你的选择数量、对手的选择数量和子问题大小,即似乎需要维护
table[p][o][n]
的最佳解决方案,其中p
是你选择的值的数量,o
是你的对手选择的数量,n
是子问题的大小。我真的需要这三个维度吗?我看到了一个类似的问题:http://www.geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/,但无法适应它。