1.题目基本信息

1.1.题目描述

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

1. 我从 1 到 n 之间选择一个数字。

2. 你来猜我选了哪个数字。

3. 如果你猜到正确的数字，就会 赢得游戏 。

4. 如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。

5. 每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。

给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。

1.2.题目地址

https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/

2.解题方法

2.1.解题思路

动态规划-区间dp

记忆化搜索（python在使用lru_cache时超时，@cache情况下AC）

2.2.解题步骤

区间dp方法步骤：

• 第一步，状态定义。dp[i][j]表示从i到j之间猜数字的情况下，确保获胜的最小现金数。

• 第二步，状态初始化。如果i>=j，则dp[i][j]=0。初始化让搜索的dp[i][j]=0。

• 第三步，状态转移。枚举当前的取法，然后在每个取出的情况下，搜索最大的可能金币数，所有取法中最小的金币数即为dp[i][j]，则可以得到转移方程：dp[i][j]=min(k+max(dp[i][k-1],dp[k+1][j]) for k in range(i,j+1))。先枚举区间长度，从2到n，长度为1的区间的金币数为1，所以不要研究了，然后枚举区间的左端点，需要保证右端点不超出范围。

• 第四步，最终的dp[1][n]即为题解

3.解题代码

python代码

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        # 思路2：动态规划-区间dp
        # 第一步，状态定义。dp[i][j]表示从i到j之间猜数字的情况下，确保获胜的最小现金数。
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        # 第二步，状态初始化。如果i>=j，则dp[i][j]=0。初始化让搜索的dp[i][j]=0。
        # 第三步，状态转移。枚举当前的取法，然后在每个取出的情况下，搜索最大的可能金币数，所有取法中最小的金币数即为dp[i][j]，则可以得到转移方程：dp[i][j]=min(k+max(dp[i][k-1],dp[k+1][j]) for k in range(i,j+1))。先枚举区间长度，从2到n，长度为1的区间的金币数为1，所以不要研究了，然后枚举区间的左端点，需要保证右端点不超出范围。
        for length in range(2, n + 1):
            for l in range(1, min(n + 1, n - length + 2)):
                r = l + length - 1
                dp[l][r] = inf
                for k in range(l, r + 1):
                    dp[l][r] = min(dp[l][r], k + max(dp[l][k - 1], dp[k + 1][r]))
        # 第四步，最终的dp[1][n]即为题解
        return dp[1][n]

    def getMoneyAmount1(self, n: int) -> int:
        # 思路1：记忆化搜索。定义f(i,j)表示从i到j之间猜数字的情况下，确保获胜的最小现金数。枚举当前的取法，然后在每个取出的情况下，搜索最大的可能金币数，所有取法中最小的金币数即为f(i,j)，则可以得到转移方程：f(i,j)=min(k+max(f(i,k-1)+f(k+1,j)) for k in range(i,j+1))。最终的f(1,n)即为题解。
        @cache
        def dfs(i:int, j:int) -> int:
            if i >= j:
                return 0
            ans = inf
            for k in range(i, j + 1):
                ans = min(ans, k + max(dfs(i, k - 1), dfs(k + 1, j)))
            return ans
        return dfs(1, n)

c++代码

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        for (int len = 2; len <= n; len++) {
            for (int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;
                dp[l][r] = INT_MAX;
                for (int k = l; k <= r; k++) {
                    dp[l][r] = min(dp[l][r], k + max(dp[l][k - 1], dp[k + 1][r]));
                }
            }
        }
        return dp[1][n];
    }
};

4.执行结果