猜数字大小 II 普普通通的区间DP。 状态： d p [ i ] [ j ] dp[i][j] dp[i][j]表示猜到某个数字的最小花费。 DP方程： d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , k + m a x ( d p [ i ] [ k − 1 ] , d p [ k + 1 ] [ j ] ) ) dp[i][j] = min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j])) dp[i][j]=min(dp[i][j],k+max(dp[i][k−1],dp[k+1][j])) 时间复杂度: O ( n 3 ) O(n^3) O(n3)
class Solution { public: int getMoneyAmount(int n) { vector<vector<int>> dp(n+1,vector<int>(n+1,(int)1e9)); for(int i=1;i<=n;i++) dp[i][i] = 0; for(int i=1;i<n;i++) dp[i][i+1] = i; for(int len = 3;len<=n;len++){ for(int i=1;i+len-1<=n;i++){ int j = i+len-1; for(int k=i+1;k<j;k++){ dp[i][j] = min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j])); } } } return dp[1][n]; } };