力扣375.猜数字大小 II
-
dp
-
dp[i][j]是说依次以从i到j的数字作为分割点(猜的数)，必定赢的游戏所用钱的最小值。
-
-
枚举每一列，从下往上算出dp[i][j]，最终答案为dp[1][n]
-
-
class Solution {public:int getMoneyAmount(int n) {if(n == 1)return 0;int dp[n+1][n+1];//初始化无穷大for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j] = INT_MAX;//i到i全为0for(int i=0;i<=n;i++)dp[i][i] = 0;//从第二列开始for(int j=2;j<=n;j++){//从下往上for(int i=j-1;i>=1;i--){//枚举除了两侧以外的分割点for(int k=i+1;k<=j-1;k++)//新的值为k+max(dp[i][k-1],dp[k+1][j])dp[i][j] = min(k+max(dp[i][k-1],dp[k+1][j]),dp[i][j]);//求两侧的dp值dp[i][j] = min({dp[i][j],i+dp[i+1][j],j+dp[i][j-1]});}}return dp[1][n];}};
