Hard DP part 2

799. Champagne Tower

https://leetcode.com/problems/champagne-tower/

I feel it hard as I didn’t figure out that I can use DP to solve this problem.

class Solution:
    def champagneTower(self, poured: int, query_row: int, query_glass: int) -> float:
        dp = [0]*101
        dp[0] = poured
        for i in range(query_row):
            new_dp = [0]*101
            for j in range(i+1):
                if dp[j]>1:
                    new_dp[j] += (dp[j]-1)/2.
                    new_dp[j+1] += (dp[j]-1)/2.
            dp = new_dp[:]
        return min(1, dp[query_glass])

1335. Minimum Difficulty of a Job Schedule

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/

class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        if n < d: return -1
        import functools
        @functools.lru_cache(None)
        def dp(i, d):
            if d==1:return max(A[i:])
            if n-i<d:return float('inf')
            return min(max(A[i:j])+dp(j,d-1) for j in range(i+1, n))
        return dp(0, d)

The above solution got TLE

31 / 32 test cases passed.
Status:Time Limit Exceeded

We can improve code below to speedup

max(A[i:j]
class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        if n < d: return -1
        import functools
        @functools.lru_cache(None)
        def dp(i, d):
            if d==1:return max(A[i:])
            if n-i<d:return float('inf')
            if n-i==d:return sum(A[i:])
            res = float('inf')
            max_ = A[i]
            for j in range(i+1, n):
                max_ = max(max_, A[j-1])
                res = min(res,max_+ dp(j,d-1))
            return res
        return dp(0, d)

runtime

Runtime: 776 ms, faster than 91.46% of Python3 online submissions for Minimum Difficulty of a Job Schedule.
Memory Usage: 13.6 MB, less than 100.00% of Python3 online submissions for Minimum Difficulty of a Job Schedule.

Or we can think in another way. First i+1 items K days.

class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        if n<d:return -1
        from functools import lru_cache
        @lru_cache(None)
        def dp(i, k):
            if k>i+1:return 1<<30
            if k==1:return max(A[:i+1])
            max_ = 0
            this_res = 1<<30
            for j in range(i, -1, -1):
                if j+1<k-1:break
                max_= max(max_, A[j])
                this_res=min(this_res, dp(j-1, k-1)+max_)
            return this_res
        return dp(n-1,d)

Complexity is O(n * n * d) if we use the improved version to do the max(A[i:j]), if not, the complexity will be O(n*n*n*d) and will get TLE.

n=300, k =10

cui aoxiang c++ solution

const int N = 300 + 10;
const int M = 20;
int dp[N][M];
int m[N][N];

class Solution {
public:
    int minDifficulty(vector<int>& a, int d) {
        int n = a.size();
        if (n < d) return -1;
        for (int i = 0; i < n; ++i) m[i][i + 1] = a[i];
        for (int k = 2; k <= n; ++k) {
            for (int i = 0; i + k <= n; ++i) {
                m[i][i + k] = max(m[i][i + k - 1], a[i + k - 1]);
            }
        }
        memset(dp, 255, sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= d; ++j) {
                dp[i][j] = 1 << 30;
                for (int k = 1; i - k >= j - 1; ++k) {
                    if (dp[i - k][j - 1] < 0) continue;
                    dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + m[i - k][i]);
                }
            }
        }
        return dp[n][d];
    }
};

Runtime of above c++ code

Runtime: 36 ms
Memory Usage: 9.2 MB

It reminds me that we can use a bottom-up DP to solve this problem.

python version can be found below. The running time is about 1000 ms.

N = 300 + 10
M = 20
dp = [[-1]*M for _ in range(N)]
m = [[0]*N for _ in range(N)]
class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        if d>n:return -1
        for i in range(n):m[i][i+1]=A[i]
        for k in range(2,n+1):
            for i in range(n-k+1):
                m[i][i+k] = max(m[i][i+k-1], A[i+k-1])
        dp[0][0] = 0
        for i in range(1,n+1):
            for j in range(1, d+1):
                dp[i][j] = (1 << 30)
                for k in range(1, i-j+2):
                    if dp[i-k][j-1]<0:continue
                    dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + m[i - k][i])
        return dp[n][d]

Or a more concise one

class Solution:
    def minDifficulty(self, A: List[int], d: int) -> int:
        n = len(A)
        if n<d:return -1
        dp = [[float('inf')]*(d+1) for _ in range(n+1)]
        dp[0][0] = 0
        for i in range(1, n+1):
            for k in range(1, d+1):
                max_ = 0
                for j in range(i-1,-1,-1):
                    if j<k-1:break
                    max_ = max(max_, A[j])
                    #print(i,j,k-1)
                    dp[i][k] = min(dp[j][k-1]+max_, dp[i][k])
        return dp[n][d]

1320. Minimum Distance to Type a Word Using Two Fingers

https://leetcode.com/problems/minimum-distance-to-type-a-word-using-two-fingers/

Top-Down DP

We have two choices — type the next character using either left or right index finger. So, we run DFS to find the minimum cost. Without memorization, the runtime complexity is O(2 ^ n).

The memorization dimensions here are quite intuitive — both fingers’ locations and position in the input string. We have 27 locations for each finger, including the initial ‘hovering’ state.

int dp[27][27][301] = {};    
int cost(char from, char to) {
    if (from == 26) return 0;
    return abs(from / 6 - to / 6) + abs(from % 6 - to % 6);
}
int minimumDistance(string &word, int pos = 0, char left = 26, char right = 26) {
    if (pos >= word.size()) return 0;
    if (dp[left][right][pos] == 0) {
        auto to = word[pos] - 'A';
        dp[left][right][pos] = min(cost(left, to) + minimumDistance(word, pos + 1, to, right),
            cost(right, to) + minimumDistance(word, pos + 1, left, to)) + 1;
    }
    return dp[left][right][pos] - 1;
}

Complexity Analysis

• Time: O(n * 27 ^ m), where m is the number of fingers. Note that this is a very loose upper bound as we won’t go through all combinations, as you will see in the next solution.
• Memory: O(n * 27 ^ m) for memoisation.

1344. Jump Game V

https://leetcode.com/problems/jump-game-v/

C++(40ms)

int res[1000];
class Solution {
public:
    int dp(vector<int>&arr, int i, int d){
        if (res[i]!=-1)return res[i];
        int this_res = 1;
        for (int k=1;k<d+1;++k){
            // positive
            if (i+k>=arr.size() || arr[i+k]>=arr[i])break;
            this_res = max(this_res, 1+dp(arr, i+k, d));
            }
        for (int k=1;k<d+1;++k){
            // negative
            if (i-k<0 || arr[i-k]>=arr[i]) break;
            this_res = max(this_res, 1+dp(arr, i-k, d));
            }
             
        res[i]=this_res;
        return this_res;
    }
    
    int maxJumps(vector<int>& arr, int d) {
        memset (res, 255, sizeof(res));
        int res = 0;
        for (int i=0;i<arr.size();++i)res=max(res, dp(arr, i,d));
        return res;
    }
};

C++ bottom up

class Solution {
public:
    int maxJumps(vector<int>&arr, int d){
        const int n= arr.size();
        vector<int> dp(n, 1);
        vector<pair<int, int>> a;
        for (int i=0;i<n;++i) a.emplace_back(arr[i], i);
        sort(a.begin(), a.end());
        for (auto [h, i]: a){
            for (int k=i+1;k<=min(i+d, n-1) &&arr[k]<h;++k)
                dp[i]=max(dp[i], 1+dp[k]);
            for (int k=i-1;k>=max(i-d, 0) &&arr[k]<h;--k)
                dp[i]=max(dp[i], 1+dp[k]);
        }
        return *max_element(dp.begin(), dp.end());
    }
        
};

Python (656ms)

from functools import lru_cache
class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        @lru_cache(None)
        def dp(i):
            this_res = 1
            for j in range(i+1, i+d+1):
                if j>=len(arr) or arr[j]>=arr[i]:break
                this_res = max(this_res, 1+dp(j))
            for j in range(i-1,i-d-1,-1):
                if j<0 or arr[j]>=arr[i]:break
                this_res = max(this_res, 1+dp(j))
            return this_res
        
        return max(dp(k) for k in range(len(arr)))