DP and binary search

1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

Naive DP solution is O(m*n*min(m,n)) will get TLE
TLE one (36 / 45 test cases passed.)

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        R, C = len(mat), len(mat[0])
        dp = [[0 for j in range(C+1)] for i in range(R+1)]
        for i in range(R):
            for j in range(C):
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j]
        cur_max = 0
        for i in range(R):
            for j in range(C):
                for L in range(cur_max+1, min(R,C)+1):
                    if i+L-1<R and j+L-1<C and dp[i+L][j+L] - dp[i+L][j] - dp[i][j+L] + dp[i][j]  <= threshold:
                        cur_max = L
        return cur_max if cur_max!=1 else 0

Reduce the complexity by using binary search can get AC. The binary search version complexity is O(m*n*log(min(m, n)))

class Solution:
    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:
        R, C = len(mat), len(mat[0])
        dp = [[0 for j in range(C+1)] for i in range(R+1)]
        for i in range(R):
            for j in range(C):
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j]
        cur_max = 0
        def binary(i, j, l, r, cur_max):
            if l>r or i+l>R or j+l>C or dp[i+l][j+l] - dp[i+l][j] - dp[i][j+l] + dp[i][j] > threshold:return cur_max
            while l<r:
                m = (l+r+1)//2
                if i+m>R or j+m>C or dp[i+m][j+m] - dp[i+m][j] - dp[i][j+m] + dp[i][j] > threshold:
                    r = m - 1
                else:
                    l = m
            return l
        for i in range(R):
            for j in range(C):
                cur_max = binary(i, j, cur_max, min(R,C)+1, cur_max)
        return cur_max if cur_max!=1 else 0

887. Super Egg Drop

Super Egg Drop - LeetCode

Naive DP will have a time complexity of O(KN²). Analysis can be found here.

Python DP from kn^2 to knlogn to kn - LeetCode Discuss

Transitions are here.

dp[i][j] = min(1 + max(dp[i-1][k-1], dp[i][j-k])), k = 1,2,...j

“First of all, we can see to get the answer of larger floors and eggs, results of smaller cases are useful for analysis, which leads to dynamic programming.

Next, how to define a state for each drop of getting the optimal floor? Here we have two variables:

• The number of eggs left to throw i, (0 <= i <= K)
• The number of floors left to test j, (1 <= j <= N)

The answer (smallest times to get the optimal floor) can be the value of each dp state.

Therefore, we define dp[i][j] as smallest number of drop to get the optimal floor with i eggs and j floors left.

DP formula

For the implementation of dp, we need two information:

• base case
• recursive relation

Base case is rather intuitive to come up with. Think of cases with smallers eggs and floors:

dp[1][j] = j, j = 1...N # one egg, check each floor from 1 to j
dp[i][0] = 0, i = 1...K # no floor, no drop needed to get the optimal floor
dp[i][1] = 1, i = 1...K # one floor, only check once

To get recursive relation, let’s consider a test case: 3 eggs and 100 floors.
For the next drop, I can choose floor from 1 to 100, say I choose 25.
There are 2 possible results for this drop:

• the egg brokes, I now have 2 eggs, and the floor to choose becomes 1~24.
• the egg remains safe, I still have 3 eggs, and the floor to choose becomes 26~100.

Think of the worst case senerio and use the dp defination above, we can describe the situation of getting the optical floor with choosing floor 25 for the next drop as:
dp[3][100] = 1 + max(dp[2][24], dp[3][75])

Besides floor 25, in term of next drop, we can also choose floor from 1 to 100. Each drop would be similar to the case of 25 above. The final result would be the minimum of all possible choices of next floors to drop:

dp[3][100] = min(..., 1 + max(dp[2][23], dp[3][76]), 1 + max(dp[2][24], dp[3][75]), 1 + max(dp[2][25], dp[3][74]), ...) (take floor 24, 25, 26 as example)

To generilize the above example, the dp formula would be:
dp[i][j] = min(1 + max(dp[i-1][k-1], dp[i][j-k])), k = 1,2,...j

The brute force solution

With dp formula above, the brute force solution would be O(kn^2) as below:“”

Naive DP TLE

from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if k == 1:return n
            if k == 0:return float('inf')
            if n == 0:return 0
            if n == 1:return 1
            return min( max(1+dp(k-1, i-1), 1+dp(k, n-i)) for i in range(1, n+1))
        return dp(K, N)

Binary search (1586ms) complexity is O(knlogn)

Kind of confusion about how to pick up the middle point.

from functools import lru_cache
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        @lru_cache(None)
        def dp(k, n):
            if k == 1:return n
            if k == 0:return float('inf')
            if n == 0:return 0
            if n == 1:return 1
            def binary(k, n):
                l, r = 1, n
                while l<r:
                    m = (l+r+1)//2
                    left, right = dp(k-1, m-1), dp(k, n-m)
                    if left > right:
                        r = m -1
                    else:
                        l = m     
                return 1+max(dp(k-1, l-1), dp(k, n-l))
            return binary(k, n)
        return dp(K, N)

It can also be done by using a smart DP (102 ms)

Explanation about this DP is here:

[C++/Java/Python] 2D and 1D DP, O(KlogN) - LeetCode Discuss

“ Imagine you have budget of m moves and k eggs (drop eggs m times and break no more than k of them) and we like to figure out maximum floor N, you like to pick a floor n to drop the first egg, the value of n can not be too big as otherwise if it broke, you can not finish the n-1 floors below it with (m-1,k-1). In fact, the largest n you can afford is dp[m-1][k-1]+1. If the first egg does not break, you can check dp[m-1][k] floors above it. So overall, the maximum floors is dp[m-1][k-1]+1+dp[m-1][k].”

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[0] * (K + 1) for i in range(N + 1)]
        for m in range(1, N + 1):
            for k in range(1, K + 1):
                dp[m][k] = dp[m - 1][k - 1] + dp[m - 1][k] + 1
            if dp[m][K] >= N: return m