Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 375. Guess Number Higher or Lower II

---

參考資訊：
https://www.cnblogs.com/grandyang/p/5677550.html

題目：


解答：

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        for (int i = 2; i <= n; ++i) {
            for (int j = i - 1; j > 0; --j) {
                int m0 = INT_MAX;

                for (int k = j + 1; k < i; ++k) {
                    int m1 = k + max(dp[j][k - 1], dp[k + 1][i]);
                    m0 = min(m0, m1);
                }

                dp[j][i] = j + 1 == i ? j : m0;
            }
        }

        return dp[1][n];
    }
};