375 Guess Number Higher or Lower II

375. Guess Number Higher or Lower II

1. Question

We are playing the Guess Game. The game is as follows:

I pick a number from 1to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay$x. You win the game when you guess the number I picked.

Example:

n = 10, I pick 8.

First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

2. Implementation

(1) Memoization

思路: 题目要求我们找出最少需要多少钱才能保证在1-n范围的数猜中数字，那么我们可以在1 - n的范围内枚举所有可能需要的cost，找出其中最小的一个即可。这里有两点需要注意的是

1.在枚举区间的过程中，我们都选择中点将区间一分为二，这个主要是为了优化算法，我们从区间的start到end逐个枚举也是可以的

2.这类问最多/最少保证结果的问题，都需要用到minmax的思想，所以当我们猜一个数字mid(代码中里mid的含义), 我们需要在两个subproblem f(start, mid - 1) 和 f(mid + 1, end)之间取两者较大值，这是为了保证能赢，我们要考虑最坏的情况。

最后这题有明显的重复subproblem存在(当n = 5时，通过画图可发现, subproblem (1, 2)出现两次), 所以需要记忆化搜索避免重复计算

class Solution {
    public int getMoneyAmount(int n) {
        int[][] cache = new int[n + 1][n + 1];
        return getMoneyByDFS(1, n, cache);
    }

    public int getMoneyByDFS(int start, int end, int[][] cache) {
        if (start >= end) {
            return 0;
        }

        if (cache[start][end] != 0) {
            return cache[start][end];
        }

        int cost = Integer.MAX_VALUE;
        int mid = start + (end - start) / 2;
        for (; mid <= end; mid++) {
            cost = Math.min(cost, mid + Math.max(getMoneyByDFS(start, mid - 1, cache), getMoneyByDFS(mid + 1, end, cache)));
        }

        cache[start][end] = cost;
        return cost;
    }
}

(2) DP

class Solution {
    public int getMoneyAmount(int n) {
        // 因为数字从1开始，为了方便计算将dp维度变成 n + 1
        // dp[i][j]代表在[i...j]这个区间里猜数字, 为了保证能赢而需要支付的最少花费
        int[][] dp = new int[n + 1][n + 1];

        for (int len = 1; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int end = start + len - 1;
                // 当start等于end时，说明猜中数，不需要任何花费
                if (start == end) {
                    continue;
                }

                dp[start][end] = Integer.MAX_VALUE;

                for (int mid = start; mid < end; mid++) {
                    // 因为是要求的是保证能赢的情况，所以我们总是要考虑最坏的情况，所以我们[start, end]的区间枚举出可能猜中的数时，
                    // 在[start, mid - 1],[mid + 1, end]两个区间中，我们取得到花费较高的区间
                    dp[start][end] = Math.min(dp[start][end], mid + Math.max(dp[start][mid - 1], dp[mid  + 1][end]));
                }
            }
        }
        return dp[1][n];
    }
}

3. Time & Space Complexity

Memoization: 时间复杂度O(), 空间复杂度O(n ^ 2)

DP: 时间复杂度O(n ^ 3), 空间复杂度O(n ^ 2)