My code:
public class Solution {
public int getMoneyAmount(int n) {
int[][] cache = new int[n + 1][n + 1];
return helper(1, n, cache);
}
private int helper(int begin, int end, int[][] cache) {
if (begin >= end) {
return 0;
}
else if (cache[begin][end] != 0) {
return cache[begin][end];
}
int ret = Integer.MAX_VALUE;
for (int i = begin; i <= end; i++) {
int cost = i + Math.max(helper(begin, i - 1, cache), helper(i + 1, end, cache));
ret = Math.min(ret, cost);
}
cache[begin][end] = ret;
return ret;
}
}
reference:
https://discuss.leetcode.com/topic/51353/simple-dp-solution-with-explanation
这道题目没能理解什么意思。
看了答案后才知道要干什么。
就是，可以这么想。
对方想骗你钱，所以嘴上说，他心里已经有个数了，让你猜。
其实，他根据你报的数，不停地改他心里的数，让你付更多的钱。
我们就需要算出这最大的钱。
于是，用户可以首先猜 m
这个时候，对方可以报小，也可以报大
但是他也只有一种选择。
所以， dp(1, m - 1) and dp(m + 1, end)
取他们的最大值就行了，然后加上 i
然后用户可以猜 1-n 里面的任何一个数，都遍历一遍，找到那个最小值，就是我们需要的最优解，最好的规划。
在这种规划下，我们一定可以拿这笔最少的钱，赢下来。
follow: 如何记录路径？
我觉得 helper 每次可以返回两个东西，一个是 min cost,
一个是 这个 cost 下的路径。
可以新建一个类，专门放这两个东西。
Anyway, Good luck, Richardo! -- 09/21/2016
