力扣每日一题2021-11-12猜数字大小II

力扣每日一题2021-11-12猜数字大小II

猜数字大小II

• 375.猜数字大小II
• • 题目描述
  • 思路：动态规划
  • • Java实现
    • Python实现

---

375.猜数字大小II 题目描述

猜数字大小II

---

思路：动态规划

如果猜数字大小k，而答案不是k的话，问题变为求解 (1, k-1) 和 (k+1, n) 的子问题需要的代价的最大值。

Java实现

class Solution {
    public int getMoneyAmount(int n) {
        int[][] f = new int[n+1][n+1];
        for (int i = n-1; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                int minCost = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = k + Math.max(f[i][k-1], f[k+1][j]);
                    minCost = Math.min(minCost, cost);
                }
                f[i][j] = minCost;
            }
        }
        return f[1][n];
    }
}

Python实现

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        f = [[0] * (n+1) for i in range(n+1)]
        for i in range(n-1, 0, -1):
            for j in range(i+1, n+1):
                f[i][j] = min(k+max(f[i][k-1], f[k+1][j]) for k in range(i, j))
        return f[1][n]