1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for(int i = n; i >= 1; --i)
{
dp[i][i] = 0;
for(int j = i + 1; j <= n; ++j)
{
int minNum = INT_MAX;
for(int k = i; k < j; ++k)
{
dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k);
}
dp[i][j] = minNum;
}
}
return dp[1][n];
}
};
|