猜数字大小 II

---

题型分析

区间DP

题目描述&数据范围

数据保证 $1\le n\le 200$

题解

考虑在区间 $[i,j]$ 获胜的代价

若猜的数字为 $x$ 且没有猜对，则要在 $[i,x-1],[x+1,j]$ 之间继续猜

转移方程为：
$$
dp[i][j]=x+max(dp[i][x-1],dp[x+1][j])
$$
更新时，从区间长度小的往区间长度大的更新

代码

int getMoneyAmount(int n) {
       vector<vector<int>>dp(n+2,vector<int>(n+2));
       for(int i=n-1;i>=1;i--){
           for(int j=i+1;j<=n;++j){
               for(int k=i;k<j;++k){
                   if(!dp[i][j])dp[i][j]=k+max(dp[i][k-1],dp[k+1][j]);
                   else dp[i][j]=min(dp[i][j],k+max(dp[i][k-1],dp[k+1][j]));
               }
           }
       }
       return dp[1][n];
   }