此题的第一反应是：难道最优解不应该是每次取最中间的数吗？其实不是，每次取最中间的数，其实得到的是最快的策略，而不一定是代价最小的策略。比如说：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 (len = 1; len<=n; len++)
{
for (start = 1; start<=n-len+1; start++)
{
int cost = INT_MAX;
for (x = start+1; x<start+len-1; x++)
cost = min( x+ max(dp[start,x-1],dp[x+1,start+len-1]));
dp[start][start+len-1] = cost;
}
}以上是主体的架构。接下来需要考虑边界条件。从主体架构中可以看出，当len<3的时候，就会出现依赖于dp[i][j], i>j的情况。所以len应该从3开始。
通过简单的考虑可知：i==j时，dp[i][j]值为零。 i==j-1时，dp[i][j]的值应该取i，即较小的那个数。