375. Guess Number Higher or Lower II

Memo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int getMoneyAmount(int n) {
        Integer[][] memo = new Integer[n + 1][n + 1];
        return getMoneyAmount(1, n, memo);
    }

    private int getMoneyAmount(int i, int j, Integer[][] memo) {
        if (i >= j) {
            // 最后一个数字，无需支付费用
            return 0;
        }

        if (memo[i][j] != null) {
            return memo[i][j];
        }

        int minCost = Integer.MAX_VALUE;
        for (int k = i; k <= j; k++) {
            // 选择数字 k 且猜错时，此时我们需要支付费用 k
            int answerInLeft = getMoneyAmount(i, k - 1, memo);
            int answerInRight = getMoneyAmount(k + 1, j, memo);
            minCost = Math.min(Math.max(answerInLeft, answerInRight) + k, minCost);
        }

        memo[i][j] = minCost;
        return minCost;
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int getMoneyAmount(int n) {
        // 定义 dp[i][j] 为 数字在 [i, j] 中时需要保证获胜的最少现金数
        // dp[i][j] depends on dp[i][k - 1] and dp[k + 1][j], k in [i, j]
        int[][] dp = new int[n + 2][n + 2]; // 此处使用 n + 2 是为了方便边界处理

        for (int i = n; i >= 1; i--) {
            for (int j = i + 1; j <= n; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) {
                    min = Math.min(min, Math.max(dp[i][k - 1], dp[k + 1][j]) + k);
                }
                dp[i][j] = min;
            }
        }

        return dp[1][n];
    }
}

References

375. Guess Number Higher or Lower II