LeetCode blog: Coins in a Line_peking2_新浪博客

LeetCode blog: Coins in a Line_peking2_新浪博客

问题：There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

这是LeetCode博客里的一道题，不在OJ里，因此一直没有做过。今天有人提到面试碰到了，我就想做做看。没有看LeetCode的分析，想先自己做。题目的要求是自己先拿硬币，那自己可以拿第一个或者最后一个，但是如何决定要拿哪一个就需要依靠子问题的结果了，这就是典型的DP思路了。首先想到了这个公式
dp[i][j]=max(A[i]+sum[i+1][j]-dp[i+1][j], A[j]+sum[i][j-1]-dp[i][j-1])

dp[i][j]代表从第i个硬币到第j个硬币这个子问题的结果，也就是可以拿到的最大钱数。那么你有两种选择
1. 如果你取第一个的话，剩下的子问题就变成了(i+1, j)了，由于轮到对方取了，因此对方可以得到dp[i+1][j]的钱数，而你则得到sum[i+1,j]-dp[i+1][j]的钱数，也就是剩余的钱数。
2. 如果你取最后一个的话，同理。
再分析方程A[i]+sum[i+1][j]=sum[i][j], A[j]+sum[i][j-1]=sum[i][j]
因此方程可以简化为
dp[i][j]=max(sum[i][j]-dp[i+1][j], sum[i][j]-dp[i][j-1])=sum[i][j]-min(dp[i+1][j],dp[i][j-1])

Read full article from LeetCode blog: Coins in a Line_peking2_新浪博客