?LeetCode刷題實(shí)戰(zhàn)375：猜數(shù)字大小 II

n = 10, 我選擇了8.

第一輪: 你猜我選擇的數(shù)字是5，我會(huì)告訴你，我的數(shù)字更大一些，然后你需要支付5塊。
第二輪: 你猜是7，我告訴你，我的數(shù)字更大一些，你支付7塊。
第三輪: 你猜是9，我告訴你，我的數(shù)字更小一些，你支付9塊。

游戲結(jié)束。8 就是我選的數(shù)字。

你最終要支付 5 + 7 + 9 = 21 塊錢(qián)。
給定 n ≥ 1，計(jì)算你至少需要擁有多少現(xiàn)金才能確保你能贏(yíng)得這個(gè)游戲。

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int> >dp(n+1, vector<int>(n+1, 0));
        vector<int> a;
        for (int i = 0; i < n; ++i) {
            a.push_back(i+1);
        }
        for (int i = 0; i < n-1; ++i) {
           dp[2][i]=a[i];
        }
        for (int len = 3; len <= n; ++len) {
            //開(kāi)始求dp[3][i]
            for (int i = 0; i <= n-len; ++i) {
                //對(duì)于每個(gè)dp[3][i]都要遍歷每個(gè)值，進(jìn)行且分，找到且分點(diǎn)的cost最小的值為dp[3][i]的值
                int global=0;
                for (int j = 0; j < len; ++j) {
                    //對(duì)于每次切分之后的兩個(gè)部分，取最大值,j是長(zhǎng)度，從下標(biāo)偏移位置為j的地方切分，左邊長(zhǎng)度為j，右邊長(zhǎng)度為len-j-1
                    //左邊開(kāi)始的值為i,右邊開(kāi)始的值為j+i+1,切分點(diǎn)為j+i
                    int tmp = max(dp[j][i], dp[len-j-1][j+i+1])+a[j+i];
                    //部分最大，整體最小
                    if(j==0) global = tmp;
                    else global = min(global, tmp);
                }
                dp[len][i] = global;
            }
        }
    
        return dp[n][0];
    }
};