这是博弈论里面的一个问题。。。。提示用DP求解，完全不会呀。。。。== 想了很久，得出的DP方程是： dp[left][right]=min(dp[left][right],i+dp[left][i-1]+dp[i+1][right]));
但是答案一直不对，于是参考了discuss，发现它的DP方程为： dp[left][right]=min(dp[left][right],i+max(dp[left][i-1],dp[i+1][right])); 和我的DP方程相比，多了一个取max操作。果然是minmax问题。。。。 由于先猜i，那么费用增加i。猜完i后，数据分成左右两部分，计算左边的最小化最大费用，右边的最小化最大费用，可以得出猜i后，费用的最大值。选着合适的i使得这个费用最小化。
最终AC代码。
class Solution { public: int getMoneyAmount(int n) { vector<int> temp(n+2,0); vector<vector<int>> dp(n+2,temp);//[1][1]-[n][n] for(int len=0;len<n;len++) { for(int left=1;left<=n;left++) { int right=left+len;//[left,right] if(right<=n) { if(left==right) dp[left][right]=0; else { dp[left][right]=INT_MAX; for(int i=left;i<=right;i++) dp[left][right]=min(dp[left][right],i+max(dp[left][i-1],dp[i+1][right])); } } } } return dp[1][n]; } };