LeetCode blog: Coins in a Line (2013-01-08 15:46:55) 这是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],
Read full article from LeetCode blog: Coins in a Line_peking2_新浪博客
No comments:
Post a Comment