题目描述

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

示例:

n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。

算法1

(dp) $O(n^3)$

一道博弈类dp
记所猜的数字为x,费用为cost
当在i~j中，选择数字k(i<=k<=j)时,有三种情况
1. k == x 猜到数字，返回cost
2. k > x 比所猜数字大，cost的值加上k,然后在i~k-1中进行猜测
3. k < x 比所猜数字小，cost的值加上k,然后在k+1~j中进行猜测
题目要求的是确保赢得这个游戏,那么当选择k时,需要在在上述3种情况中选择最大值.然后,k有j-i+1种选择,我们在这j-i+1种选择中选择其结果最小的值,这个值为在i~j中确保赢得游戏的最小花费.
我们用dp[i][j]表示i~j中确保赢得游戏的最小花费.那么状态转移方程为
dp[i][j] = min( dp[ i ][ j ], max( dp[ k + 1 ][ j ], dp[ i ][ k - 1 ] ) + k )
初始化dp[ i ][ i ] = 0;
然后以范围从小到大进行表示即可

C++ 代码

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for( int i = 1; i <= n; ++ i ) dp[ i ][ i ] = 0;
        for( int i = 1; i <= n - 1; ++ i )  //范围从小到大
        {
            for( int j = 1; j + i <= n; ++ j )
            {
                dp[ j ][ j + i ] = INT_MAX;
                for( int k = j; k <= j + i; ++ k )
                {
                    int tmp = k;
                    if( k != j + i ) tmp = max( tmp, k + dp[ k + 1 ][ j + i ] );
                    if( k != j )     tmp = max( tmp, k + dp[ j ][ k - 1 ] );
                    dp[ j ][ j + i ] = min( dp[ j ][ j + i ], tmp );
                }
            }
        }
        return dp[ 1 ][ n ];
    }
};