区间dp + 记忆性搜索
搭眼一看,是个最大值最小化
dp[1][n]表示区间[1, n]所需要至少的money
因为不知道最后一步选哪个,则枚举1-n的数
则dp[1][n] = min(dp[1][n], k + max(dp[1][k - 1], dp[k + 1][n]))
注意边界
用dfs从小区间到大区间,同时记录一下已完成的区间
class Solution { public: int dp[500][500]; int dfs(int i, int j) { if(i == j) return 0; if(dp[i][j]) return dp[i][j]; for(int k = i; k <= j; k++) { if(k == i) dp[i][j] = k + dfs(k + 1, j); else if(k == j) dp[i][j] = min(dp[i][j], k + dfs(i, k - 1)); else dp[i][j] = min(dp[i][j], k + max(dfs(i, k - 1), dfs(k + 1, j))); } return dp[i][j]; } int getMoneyAmount(int n) { memset(dp, 0, sizeof(dp)); return dfs(1, n); } };