此题的第一反应是：难道最优解不应该是每次取最中间的数吗？其实不是，每次取最中间的数，其实得到的是最快的策略，而不一定是代价最小的策略。比如说：1,2,3,4,5，按每次取最中间的策略，代价应该是3+4=7；但更优的策略应该是2+4=6.
那么应该怎么决策呢？那就要紧紧结合这个“代价函数”来考虑。假设F(1,n)表示对于从1~n的进行猜数游戏所需要付出的最小代价，我们应该怎么从中选择第一个数x才是最优的呢？假设我们选择了报数x，那么对应的代价是什么。显然，当前付出的的代价是x，那么之后呢？这就涉及到了对剩下两个区间的选择，之后的代价是F(1,x-1)还是F(x+1,n)？根据题意，其实应该是两者的最大值 max(F(1,x-1),F(x+1,n))。于是整个递归的思路就已经呼之欲出了：
F(1,n) = min( x + max(F(1,x-1),F(x+1,n)) ) for x=1,2,...,n
有了递归的思路，我们再考虑是否能够用DP来实现（本质就是加记忆化），来避免重复的搜索。很显然，递归的关系已经揭示了该如何自下而上地填充DP数组。
dp[i][j]表示对于i~j的区间进行猜数游戏所需要的最小代价。最终的结果就是返回dp[1][n]。从递归关系来看，我们应该先从小的区间片段开始填充，不断得到较大的、更大的区间片段，直至得到dp[1][n]。所以这个多层的for循环架构，最外层的应该是控制区间的长度len。
for (int len=2; len<=n; len++)
for (int i=1; i+len-1<=n; i++)
{
int j = i+len-1;
dp[i][j] = INT_MAX/2;
for (int k=i; k<=j; k++)
dp[i][j] = min(dp[i][j] , k + max(dp[i][k-1], dp[k+1][j]));
} 以上是主体的架构。接下来需要考虑边界条件。边界条件主要是两个：一个是i==j的时候，即len==1，此时注意dp[i][j]=0（只有一个候选，不用猜就知道答案）。另外就是i>j，这种情况出现在k在[i:j]边界的时候，观察状态转移方程，应该使dp[i][j]不影响结果，可以设置为0.