刷题记录

思路 ： 几乎和stone game一模一样。因为允许circle，所以在这里扩展一次数组。比如[4,4,5,9]，就变成了[4,4,5,9,4,4,5,9]。区间还是1~n。 实现 ： 所求得的最终结果是每个区间的最小值。

虽然是hard，但是真正理解起来并不难。关键是要知道区间dp的概念。因为棋手是前后端都可以选，单个状态dp不好表示，所以利用区间dp[i][j]表示在i->j这个区间先手能取到的最大值。 dp[i][j]=sum[i][j]-min(dp[i][j-1],dp[i+1][j])。这道题用记忆化搜索的递归方法来实现。

记忆化搜索。 1. 不能赋初始值，因为dp[0][0]有可能成为终点，走的方向是上下左右。 2. 实现的时候在search函数里面，要把求得的值赋给dp[x][y]。因为如果在search里面调用search，"res=Math.max(res,search(newx,newy,A)+1);",这里求得的结果其实是dp[x][y],如果不赋值给dp[x][y]，那么就白调用了。