g*****y
发帖数: 94 | 1 在网上看到的面试题：
两个选手A和B轮流从N块石头中每次拾取[1, k]块石头，A先拾取。A和B每次都是采取最
优策略。拾取最后一块石头的选手定为失败，写一个function决定A是否可以取胜。
问问大家怎么Approach？暴力法可以比较容易，但是复杂度太高。 |
k******4
发帖数: 94 | 2 N=1，A输，
N>1，A第一次选（N-1）mod （k+1）块，以后每次B选x块的时候，A就选k+1-x块，最后
一块肯定是B的。
【在 g*****y 的大作中提到】
: 在网上看到的面试题：
: 两个选手A和B轮流从N块石头中每次拾取[1, k]块石头，A先拾取。A和B每次都是采取最
: 优策略。拾取最后一块石头的选手定为失败，写一个function决定A是否可以取胜。
: 问问大家怎么Approach？暴力法可以比较容易，但是复杂度太高。
|
g*****y
发帖数: 94 | 3 多谢你的solution，我觉得你的解法已经非常接近啦。如果A和B可以选[0, k]块的话，
那么你的solution works，因为但N=k+2的时候，(N-1) mod (k+1) 等于0，对于原题来
说肯定不行。不过根据你的解法，我想到的方法是当 (N-1) mod (k+1) == 0的时候，A
肯定会输，其他的情况只要按照你的解法选取石头，A肯定会赢。
【在 k******4 的大作中提到】
: N=1，A输，
: N>1，A第一次选（N-1）mod （k+1）块，以后每次B选x块的时候，A就选k+1-x块，最后
: 一块肯定是B的。
|
k******4
发帖数: 94 | 4 有道理，我前面想错了。谢谢纠正
，A
【在 g*****y 的大作中提到】
: 多谢你的solution，我觉得你的解法已经非常接近啦。如果A和B可以选[0, k]块的话，
: 那么你的solution works，因为但N=k+2的时候，(N-1) mod (k+1) 等于0，对于原题来
: 说肯定不行。不过根据你的解法，我想到的方法是当 (N-1) mod (k+1) == 0的时候，A
: 肯定会输，其他的情况只要按照你的解法选取石头，A肯定会赢。
|
c****8
发帖数: 76 | 5 如果不用上面的那些帖子给的公式的话，下面的DP应该可以解决，time complexity O(
nk), space complexity O(n)，不知道大家有没有更好的解法？
// Dynamic programming
public boolean canWinDP(int n, int k) {
if (n <= 0) {
return true;
} else if (n == 1) {
return false;
}
boolean[] f = new boolean[n + 1];
f[0] = true;
f[1] = false;
for (int i = 2; i <= n; ++i) {
boolean mustPick = true;
for (int j = i - 1; j >= 1 && j >= i - k; --j) {
mustPick &= f[j];
}
f[i] = !mustPick;
}
return f[n];
} |
