Guess Number Higher or Lower II

This approach solves the problem iteratively using bottom-up dynamic programming, also known as tabulation. It avoids recursion and its associated overhead, often leading to better performance. We use a 2D table, dp[i][j], to store the minimum cost to guarantee a win for the number range [i, j]. The key idea is to fill this table by starting with the smallest subproblems (ranges of length 2) and progressively building up to the solution for the full range [1, n]. By iterating through range lengths, we ensure that when we calculate dp[i][j], the solutions for all smaller, required subproblems (like dp[i][k-1] and dp[k+1][j]) have already been computed and stored in the table.

1. Create a 2D DP table dp of size (n+2) x (n+2) and initialize all its values to 0. The extra padding helps handle boundary cases like k-1 and k+1 without extra checks.
2. Iterate over the length of the range, len, from 2 to n.
3. Inside this loop, iterate over all possible starting points i for a range of length len. The loop for i will go from 1 up to n - len + 1.
4. Calculate the end point of the current range: j = i + len - 1.
5. For the current range [i, j], initialize its cost dp[i][j] to Integer.MAX_VALUE.
6. Iterate through all possible first guesses k from i to j.
7. For each guess k, calculate the cost using the already computed values from smaller sub-ranges: cost = k + max(dp[i][k-1], dp[k+1][j]).
8. Update the minimum cost for the range [i, j]: dp[i][j] = min(dp[i][j], cost).
9. After all loops complete, the value dp[1][n] will contain the minimum cost to guarantee a win for the entire range [1, n]. Return this value.

Instead of starting from the top problem (1, n) and breaking it down, the bottom-up approach starts with the smallest problems and builds up. We use a 2D array dp[n+2][n+2] where dp[i][j] stores the solution for the subproblem on the range [i, j]. The base cases are ranges of length 0 or 1, for which the cost is 0. Our DP table is initialized to 0, which covers these cases. We then iterate on the length of the range, len, from 2 to n. For each len, we iterate through all possible start indices i. The end index j is simply i + len - 1. For each range [i, j], we calculate dp[i][j] by trying every possible split point k (our first guess) from i to j. The cost for guessing k is k + max(dp[i][k-1], dp[k+1][j]). Since we are iterating by increasing length, the values dp[i][k-1] (for range length k-i) and dp[k+1][j] (for range length j-k) are guaranteed to have been computed in previous iterations. We take the minimum cost over all possible k. The final answer is the value stored in dp[1][n].

public class Solution {
    public int getMoneyAmount(int n) {
        if (n == 1) {
            return 0;
        }
        // dp[i][j] = min cost for range [i, j]
        int[][] dp = new int[n + 2][n + 2];

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

        return dp[1][n];
    }
}