LeetCode 0375 - Guess Number Higher or Lower II

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.

class Solution {
public:
    int getMoneyAmount(int n) {
        auto dp = std::vector<std::vector<int>>(n + 1, std::vector<int>(n + 1, 0));
        for(int i = 2; i <= n; i++) {
            for(int j = i - 1; j >= 1; j--) {
                if(j == i - 1) {
                    dp[j][i] = j;
                } else {
                    int global_min = INT_MAX;
                    for(int k = j + 1; k < i; k++) {
                        int local_max = k + std::max(dp[j][k - 1], dp[k + 1][i]);
                        global_min = std::min(global_min, local_max);
                    }                                    
                    dp[j][i] = global_min;
                }                                        
            }
        }

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