375. 猜数字大小 II
class Solution {
public:
int getMoneyAmount(int n) {
int dp[n + 2][n + 2];
memset(dp, 0, sizeof dp);
for (int len = 2; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
dp[i][j] = 1e9;
for (int k = i; k <= j; k++) {
dp[i][j] = min(dp[i][j], k + max(dp[i][k - 1], dp[k + 1][j]));
}
}
}
return dp[1][n];
}
};
网友评论