刷
July-31-2019
这种题遇到就两腿一蹬，地上一躺。 和coins-in-a-line-I除了名字很像，没啥屌关系，如果真的作为I的follow up，就太坑了，因为根本不是FOLLOW UP，用1的思路去考虑就崩了。
dp[n]代表剩下n个硬币的时候的最大收益。
n的时候，有2种情况，可以选择拿1个，也可以选择拿2个:
- 拿1个，然后对方会选择拿1个或者拿2个, 此时我的收益就是：
- 当前1个硬币价值 + 剩n-2个 和 剩n-3个中较小的一个，因为分别对应对方拿1个或者2个，而对方他妈又不是傻逼，会选择1个或者2个中收益多的
- 拿2个，然后对方会选择拿1个或者拿2个，此时我的收益就是：
- 当前2个硬币的价值 + 剩n-3和n-4中较小的。
dp[n]是上面2种情况中拿1个或者拿2个收益高的
这种题做的太少，不好总结。
一开始的012是为了防止出现只有1个硬币却尝试拿2个的情况。
仔细看会发现dp[n-1]永远没被用过，也很诡异。
public class Solution {
public boolean firstWillWin(int[] values) {
// write your code here
if (values == null) return false;
if (values.length <= 2) return true;
int total = values.length;
// dp[X] x coins left
int[] dp = new int[total + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
dp[1] = values[total-1];
dp[2] = values[total-1] + values[total-2];
dp[total] = getProfit(total, dp, values);
int valueCount = 0;
for (int i : values) valueCount += i;
return dp[total] * 2 > valueCount;
}
public int getProfit(int remain, int[] dp, int[] values) {
if (remain <= 0) return 0;
if (dp[remain] != -1) return dp[remain];
int coinCount = values.length;
// pick 1, the other people will choose max from pick next 1 or next 2
// which leaves us min from pick 1
int pickOne = values[coinCount - remain]
+ Math.min(getProfit(remain-1-1, dp, values),
getProfit(remain-1-2, dp, values));
int pickTwo = values[coinCount - remain] + values[coinCount - remain + 1]
+ Math.min(getProfit(remain-2-1, dp, values),
getProfit(remain-2-2, dp, values));
dp[remain] = Math.max(pickOne, pickTwo);
return dp[remain];
}
}
最后更新
2016-12-22
这个题做得也不好，dp[n]尝试写了几下，不太对。
应该是类似于gem theory的题。
当只有1个硬币剩下的时候直接拿走，不BB。
剩俩的时候也都拿了。。
dp[n]表示剩下多少个硬币。
轮到我们拿第i个硬币的时候，有2种情况：
- 我们拿这个 i 。
- 对手选择拿1个，就是第i+1个，然后第i+ 2轮到我们，我们再决定。
- 对手选择拿2个，i+1和i+2, 然后i+3轮到我们。
- 我们拿这个i，再拿下一个i+1。
- 对手选择拿1个，就是第i+2, 然后i+3轮到我们。
- 对手选择拿2个，i+2, i+3，然后i+4该我们选择了。
当前怎么选取决于拿1个得的多还是拿2个得的多：
dp[i] = Math.max(拿1个， 拿2个)
但是注意中间对手拿的时候，他也要选择对他有利的，所以再轮到我们的时候，我们就拿得相对小的那个选择。
拿1个 = 当前的1个硬币 + Math.min(第i+2轮到我们，第i+3轮到我们)
拿2个 = 当前的2个硬币 + Math.min(第i+3轮到我们, 第i+4轮到我们）
思路很绕，是一个极小极大的思路，minimax。
另一个地方是并没有急于计算对手能拿多少而减去他的决定，而是尝试在他的选择下直接获取我们的硬币，最后看看拿的数量过不过半。
一头雾水。。。
public class Solution {
public boolean firstWillWin(int[] values) {
if (values.length <= 2) return true;
// max profit when there are n coins left
int[] dp = new int[values.length + 1];
Arrays.fill(dp, -1);
int total = values.length;
dp[0] = 0;
// only 1 left, we get that one
dp[1] = values[total-1];
// only 2 left, we grab those 2 fucking coins
dp[2] = values[total-2] + values[total-1];
// wat will we get when there are n left..
dp[total] = nthProfit(total, dp, values);
int sum = 0;
for (int i : values) sum += i;
return dp[total] > sum/2;
}
public int nthProfit(int leftOver, int[] dp, int[] values) {
if (leftOver <= 0) return 0;
if (dp[leftOver] != -1) return dp[leftOver];
int total = values.length;
int pickOne = values[total - leftOver] +
Math.min(nthProfit(leftOver-2, dp, values),
nthProfit(leftOver-3, dp, values));
int pickTwo = values[total - leftOver] + values[total - leftOver + 1] +
Math.min(nthProfit(leftOver-3, dp, values),
nthProfit(leftOver-4, dp, values));
dp[leftOver] = Math.max(pickOne, pickTwo);
return dp[leftOver];
}
}