Problem statement

https://leetcode.com/problems/guess-number-higher-or-lower-ii/

Solution 1

First solution is to use dp with state dp(a, b), where it is answer to subproblem [a, b]. Then we need to solve minimax problem.

Complexity

Time complexity is O(n^3), space is O(n^2).

Code

class Solution:
    def getMoneyAmount(self, n):
        @lru_cache(None)
        def dp(a, b):
            if b - a <= 0: return 0
            return min(max(dp(a, k-1), dp(k+1, b)) + k for k in range(a, b+1))
        
        return dp(1, n)

Solution 2

What we need to solve is:

\[f(a, b) = \min\limits_{a\leqslant k \leqslant b} \left(\max\{f(a, k-1), f(k+1, b) \} + k \right).\]

To optimize the computations, denote

\[k_0(a, b) = \max\{k: f(a, k-1) \leqslant f(k+1, b)\},\]

then

\[\max\{f(a, k-1), f(k+1, b)\} = \left\{ \begin{array}{ccc}f(k+1, b) & \text{ if } & a\leqslant k \leqslant k_0(a,b)\\ f(a, k-1) & \text{ if } & k_0(a, b) < k \leqslant b \end{array} \right.\]

Then, we can rewrite:

\[f(a, b) = \min\{f_1(a, b), f_2(a, b)\}\] \[f_1(a, b) = \min\limits_{a\leqslant k \leqslant k_0(a,b)} (f(k+1, b) + k)\] \[f_2(a, b) = \min\limits_{k_0(a,b) < k \leqslant b} (f(a, k-1) + k) = f(a, k_0(a,b)) + k_0(a,b) + 1.\]

Notice, that $k_0(a_1, b) \leqslant k_0(a_2, b)$ if $a_1 \leqslant a_2$. So, we can compute $k_0(a, b)$ in amortized $O(1)$ time. Then we need the sliding minimum of $g(k, b) = f(k+1, b) + k$ with $b$ fixed and $a\leqslant k \leqslant k_0(a,b)$. This can be done using and increasing deque idea and this will take $O(1)$ amortized time to get this minimum. So, we need to compute $O(n^2)$ values of $f$ in total $O(n^2)$ time complexity.

Complexity

Time complexity is $O(n^2)$, space as well.

Code

class Solution:
    def getMoneyAmount(self, n):
        dp = [[0] * (n+1) for _ in range(n+1)] 
        for r in range(2, n+1):
            k = r - 1
            deq = deque()
            for l in range(r-1, 0, -1):
                while k > 0 and dp[l][k-1] > dp[k+1][r]:
                    k -= 1
                while deq and deq[0][0] > k:
                    deq.popleft()
                deqVal = dp[l+1][r] + l
                while deq and deq[-1][1] > deqVal:
                    deq.pop()
                deq.append((l, deqVal))
                dp[l][r] = min(dp[l][k] + k + 1, deq[0][1])
        return dp[1][n]