LeetCode 375. 猜数字大小 II（DP）

示例:
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

class Solution {
public:
    int getMoneyAmount(int n) {
    	vector<vector<int>> dp(n+1, vector<int>(n+1, INT_MAX));
    	// dp[i][j] 表示答案在 区间 [i,j] 内所需的最小花费
    	for(int i = 1; i <= n; i++) 
    		dp[i][i] = 0;//初始化
    	for(int len = 1; len <= n; len++) 
    	{
    		for(int i = 1; i <= n-len; i++)
    		{
    			int j = i+len;
    			dp[i][j] = min(i + dp[i+1][j], dp[i][j-1] + j);//区间端点
    			for(int k = i+1; k < j; k++)
    			{
    				dp[i][j] = min(dp[i][j], max(dp[i][k-1], dp[k+1][j])+k);
    										// [i,k-1]  k  [k+1, j]
    			}
    		}
    	}
    	return dp[1][n];
    }
};