思路：

dp。

实现：

1 class Solution  2 { 3 public: 4     int getMoneyAmount(int n)  5     { 6         int dp[n + 1][n + 1]; 7         memset(dp, 0x3f, sizeof dp); 8         for (int i = 0; i <= n; i++) 9             dp[i][i] = 0;10         for (int i = n - 1; i >= 1; i--)11         {12             for (int j = i + 1; j <= n; j++)13             {14                 for (int k = i; k <= j; k++)15                 {16                     dp[i][j] = min(dp[i][j], k + 17                                    max(i > k - 1 ? 0 : dp[i][k - 1], 18                                        k + 1 > j ? 0 : dp[k + 1][j]));19                 }20             }21         }22         return dp[1][n];23     }24 };

 实现2：

1 class Solution 2 { 3 public: 4     int dfs(int l, int r, vector
     
      
       > & dp) 5     { 6         if (l == r) return 0; 7         if (dp[l][r] != -1) return dp[l][r]; 8         int ans = 0x3f3f3f3f; 9         ans = min(ans, l + dfs(l + 1, r, dp));10         ans = min(ans, r + dfs(l, r - 1, dp));11         for (int i = l + 1; i <= r - 1; i++)12         {13             ans = min(ans, max(dfs(l, i - 1, dp), dfs(i + 1, r, dp)) + i);14         }15         return dp[l][r] = ans;16     }17     int getMoneyAmount(int n) 18     {19         vector
       
        
         > dp(n + 1, vector
         
          (n + 1, -1));20         return dfs(1, n, dp);21     }22 };