🌕🌗 375. 猜数字大小 II

难度: 🌕🌗

问题描述

---

解法

class Solution {
    public int getMoneyAmount(int n) {
        // 思路：
        // dp[i][j] = max(dp[i][k], dp[k + 1][j]) 取所有 k 情况下的 min
        int[][] dp = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i ++) {
            Arrays.fill(dp[i], -1);
        }
        // dp
        for(int i = n; i >= 0; i --) { // i == 0 时 dp[0][j] === 0 没有任何过程会用到因此值为任何值均无影响
            for(int j = i; j <= n; j ++) {
                if(i == j) {
                    dp[i][j] = 0;
                } else if(i == j - 1) {
                    dp[i][j] = i; // 猜较大的数，猜中不输钱，不中需要付较小数对应的前
                } else {
                    // 至少 3 个值
                    // 假设当前选中 k，若极端情况下 k 没有猜中，游戏会告知往哪个方向走，因此需要确保不论哪个方向本金仍足够
                    for(int k = i; k <= j; k ++) {
                        int tmp = k; // 初始情况下需要付出猜不中的代价
                        if(k > i) {
                            tmp += dp[i][k - 1];
                        }
                        if(k + 1 <= j) {
                            // 判断是否同样为 k > i
                            if(k > i && dp[i][k - 1] < dp[k + 1][j]) {
                                tmp = tmp - dp[i][k - 1] + dp[k + 1][j]; // 保留右节点
                            } else if(k <= i) {
                                tmp += dp[k + 1][j];
                            }
                        }
                        if(dp[i][j] == -1) {
                            dp[i][j] = tmp;
                        } else {
                            dp[i][j] = Math.min(dp[i][j], tmp);
                        }
                    }
                }
                // System.out.println(i + ":" + j + "  " + dp[i][j]);
            }
        }
        return dp[1][n];
    }
}

---

输出