We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5. Second round: You guess 7, I tell you that it's higher. You pay $7. Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Constraints:
1 <= n <= 200
A:
就是检验各种情况,然后找出所有的来。
class Solution { public: int getMoneyAmount(int n) { vector<vector<int>> V(n+1,vector<int>(n+1,-1)); return helper(1,n,V); } private: int helper(int start, int end, vector<vector<int>> &V){ if(start >= end) return 0; if(V[start][end] >=0) return V[start][end]; int res = INT_MAX; for(int i =start; i<=end;i++){ int tmp = i + max(helper(start, i-1, V) , helper(i+1, end, V)); res = min(res, tmp); } V[start][end] = res; return res; } };
当然,这个题目,vector<vector<int>> V 也可以不用递归, 用DP来填上。
Error:
一开始,我res = min(res, tmp) . 我写成max 了。 糊涂啊~~~~~
No comments:
Post a Comment