Leetcode 375 猜数字大小2 （动态规划）

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for (int i = 1;i <= n;i++) {
            dp[i][i] = 0;
            if (i != n) {
                dp[i][i + 1] = i;
            }
        }
        for (int k = 3;k <= n;k++) {
            for (int i = 1;i <= n-k+1;i++) {
                int minn = (1<<30)-1;
                for (int j = i + 1;j < i + k - 1;j++) {
                    int tmp = j + max(dp[i][j - 1], dp[j + 1][i + k - 1]);
                    if (tmp < minn)minn = tmp;
                }
                dp[i][i + k - 1] = minn;
            }
        }
        return dp[1][n];
    }
};