[ Leetcode ] Dynamic Programming

Posted on | In , |

Target problems

Dynamic Programming is targeting to solve most of the Optimization Problems.

  • Simple Subproblems: there should be a simple way of defining subproblems with just a few indices like i, j, k…
  • Subproblem Optimization
  • Subproblem Overlap: optimal solutions to unrelated subproblems can contain subproblems in common

It uses Memoization Algorithm, which means store and return the value rather than compute them again.

Template solution:

  • Store temp data in a temp[] array
  • Introduction
  • The process of solving easier-to-solve sub-problems and building up the answer from that

Count Path

1
2
3
4
5
6
7
8
int countPaths(boolean[][] grid, int row, int col, int[][]paths) {
  if (!validSquared(grid, row, col)) return 0;
  if(isAtEnd(grid, row, col)) return 1;
  if (paths[row][col]==0) { // store the computed value
    paths[row][col] = countPaths(grid, row + 1, col) + countPaths(grid, row, col + 1);
  }
  return paths[row][col];
}

Fibbonaci

Thoughts to be added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Fibbonaci using memoization
def fib(n, memo):
  if memo[n] != null:
    return memo[n]
  if n==1 or n==2: # executed at most n times
    reult = 1
  else:
    result = fib(n-1) + fib(n - 2)
  memo[n] = result
  return result

# Fibbonaci bottom_up solution
def fib_bottom_up(n):
  if n==1 or n==2:
    return 1
  bottom_up = new int[n + 1]
  bottom_up[1] = 1
  bottom_up[2] = 1
  for i from 3 upto n:
    bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
  return bottom_up[n]

53. Maximum Subarray

1
2
3
4
5
6
7
8
9
10
11
12
public int maxSubArray(int[] A) {
  int n = A.length;
  int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
  dp[0] = A[0];
  int max = dp[0];

  for(int i = 1; i < n; i++){
      dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
      max = Math.max(max, dp[i]);
  }
  return max;
}

64. Minimum Path Sum

Thoughts to be added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        if (grid.length == 1) {
            int result = 0;
            for(int i: grid[0]) result += i;
            return result;
        }
        if (grid[0].length == 1) {
            int result = 0;
            for(int[] row: grid) result += row[0];
            return result;
        }
        int[][] temp = new int[grid.length][grid[0].length];
        int max = Integer.MAX_VALUE;
        for (int[] row: temp) Arrays.fill(row, max);
        temp[grid.length - 1][grid[0].length - 1] = grid[grid.length - 1][grid[0].length - 1]; // initialize last element

        for (int i = grid.length - 1; i > 0; i--) {
            for (int j = grid[0].length - 1; j > 0; j--) {
                if (temp[i][j - 1] == max) temp[i][j - 1] = temp[i][j] + grid[i][j - 1]; // calculate left one
                if (temp[i - 1][j] == max) temp[i - 1][j] = temp[i][j] + grid[i - 1][j]; // calculate top one
                temp[i - 1][j - 1] = Math.min(temp[i - 1][j], temp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return temp[0][0];
    }
}

63. Unique Paths II

Thoughts to be added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int uniquePathsWithObstacles(int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        if (grid[0][0] == 1) return 0;

        int[][] temp = new int[grid.length][grid[0].length];
        temp[grid.length - 1][grid[0].length - 1] = 1;
        for (int i = temp.length - 1; i >= 0; i --) { // start from the end
            for (int j = temp[0].length - 1; j >= 0; j--) {

                if (grid[i][j] == 1) {
                    temp[i][j] = 0;
                    continue;
                }
                if (i == grid.length - 1 || grid[i + 1][j] == 1) {
                    if (j + 1 == grid[0].length) continue; // skip the last cell
                    temp[i][j] = temp[i][j + 1];
                    continue;
                }
                if (j == grid[0].length - 1 || grid[i + 1][j] == 1) {
                    temp[i][j] = temp[i + 1][j];
                    continue;
                }
                temp[i][j] = temp[i + 1][j] + temp[i][j + 1];
            }
        }
        return temp[0][0];
    }
}

62. Unique Paths

1
TBA

95. Unique Binary Search Trees II

Leetcode: https://leetcode.com/problems/unique-binary-search-trees-ii/description/
Introduction: https://www.youtube.com/watch?v=GZ0qvkTAjmw

[Solution] See: https://leetcode.com/problems/unique-binary-search-trees-ii/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<TreeNode>();
        return helper(1,n);
    }
    private List<TreeNode> helper(int a, int b) {
        List<TreeNode>res = new ArrayList<TreeNode>();

        if (a > b) {
            res.add(null); // add null to ensure the for loop can go on even if the left node is null
            return res;
        }

        for (int i = a; i <= b; i++) {
            // select root
            List<TreeNode> left = helper(a, i-1);
            List<TreeNode> right = helper(i+1, b);

            for (TreeNode l: left) {
                for (TreeNode r: right) {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

96. Unique Binary Search Trees

Leetcode: https://leetcode.com/problems/unique-binary-search-trees/description/

[Solution] See https://leetcode.com/articles/unique-binary-search-trees/

1
2
3
4
5
6
7
8
let F(i, n): nums of unique BST of root = i, in range n
let G(n): nums of unique BST in range n
F(i, n) = G(i-1) * G(n-i)
Also, since G(n) = Sum(F(i,n), i->n)
G(n) = Sum(G(i-1) * G(n-i))
let i = n; j = i, we can get:

G(i) = Sum(G(j-1) * G(i - j))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                G[i] += G[j-1]*G[i-j];
            }
        }
        return G[n];
    }
}

Subsequence problem

115. Distinct Subsequence

Leetcode: https://leetcode.com/problems/distinct-subsequences/description/

[Solution] https://www.youtube.com/watch?v=mPqqXh8XvWY&t=187s

1
2
3
4
5
6
7
Use a (m + 1) * (n + 1) 2-D array to store results

  - b a b g b a g
- 1 1 1 1 1 1 1 1
b 0 1 1 2 2 3 3 3
a 0 0 1 1 1 1 4 4
g 0 0 0 0 1 1 1 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length() + 1; // m s j
        int n = t.length() + 1; // n t i
        int[][] res = new int[n][m];

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j++) {
                if (j == 0) {
                    res[i][j] = 0;
                }
                if (i == 0) {
                    res[i][j] = 1;
                }

                if ( i > 0 && j > 0 && s.charAt(j - 1) == t.charAt(i - 1)) {
                    res[i][j] = res[i - 1][j - 1] + res[i][j - 1];
                } else if (i > 0 && j > 0) {
                    res[i][j] = res[i][j - 1];
                }
            }
        }
        // DEBUG
        // for (int[] r: res) {
        //     System.out.println(Arrays.toString(r));
        // }
        return res[n - 1][m - 1];
    }
}

1143. Longest Common Subsequence

Leetcode: https://leetcode.com/problems/longest-common-subsequence/

1
2
3
4
5
6
7
8
9
10
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
    
    for i in range(1, len(text1) + 1):
        for j in range(1, len(text2) + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]

With space optimization

1
2


279. Perfect Squares

Leetcode: https://leetcode.com/problems/perfect-squares/description/
Video: https://www.youtube.com/watch?v=jVnZxPxzyDA

1-D DP problem using intermediate state transfer

[Solution]

  1. dp[i]: The least number of perfect square numbers of a given integer i
  2. state transfer equation dp[i] = min(dp[i + j * j]) (j = 1 -> sqrt(i)) Using intermemiate state
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        // Construct dp array
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= Math.sqrt(i); j++) {
                min = Math.min(min, dp[i - j * j] + 1);
            }
            dp[i] = min;
        }
        return dp[n];
    } 
}

139. Word Break

Leetcode: https://leetcode.com/problems/word-break/description/

Video: https://www.youtube.com/watch?v=WepWFGxiwRs

[Solution]
https://leetcode.com/problems/word-break/solution/

  1. Use two for-loops to check if there exist a point where can split current substring into two parts and those two parts are also in the dictionary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        i = 0
        dp = [False]*(len(s) + 1)
        dp[0] = True
        
        while i < len(s) + 1: #s[:i] substring
            j = 0
            while j < i: # s[:j], s[j:i]
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
                j += 1
            i += 1
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
var wordBreak = function(s, wordDict) {
    let set = new Set(["", ...wordDict]);
    let dp = new Array(s.length).fill(false);
    for (let i = 0; i < s.length; i++ ) {
        for (let j = 0; j <= i + 1; j++) {
            if (set.has(s.substring(0, j) ) && set.has(s.substring(j, i + 1))) {
                dp[i] = true;
                set.add(s.substring(0, i + 1))
            }
        }
    }
    return dp[dp.length - 1];
};

140. Word Break II

Leetcode: https://leetcode.com/problems/word-break-ii/

String = prefix + tail

472. Concatenated Words

Leetcode: https://leetcode.com/problems/concatenated-words/

  1. A string can only be formed by string shorter than itself
  2. DP array: dp[i]: a boolean value indicate if s[i] can be formed by what’s in the dict
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
    words.sort(key=lambda x: len(x))
    
    def canForm(word, wordDict):
        if not wordDict:
            return False
        dp = [False for _ in range(len(word) + 1)]
        dp[0] = True
        for i in range(1, len(word) + 1):
            for j in range(i):
                if not dp[j]:
                    continue
                if word[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp[-1]
    res = []
    candidates = set()
    for i, word in enumerate(words):
        if canForm(word, candidates):
            res.append(word)
        candidates.add(word)
    return res

String Match Problem

10. Regular Expression Matching

String match usually use DP to solve.

Leetcode: https://leetcode.com/problems/regular-expression-matching/description/
Video: https://www.youtube.com/watch?v=DqhPJ8MzDKM

  • State
  • Init
  • Function
  • Result

Note:

  • Need to deal with a lot edge cases (index overflow)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def isMatch(self, s: str, p: str) -> bool:
    dp = [[False for j in range(len(s) + 1)] for i in range(len(p) + 1)]
    dp[0][0] = True

    for i in range(1, len(p) + 1):
        if p[i - 1] == "*":
            if i == 1:
                dp[i][0] = True
            else:
                dp[i][0] = dp[i - 2][0]

    for i in range(1, len(p) + 1):
        for j in range(1, len(s) + 1):
            if s[j - 1] == p[i - 1] or p[i - 1] == ".":
                dp[i][j] = dp[i - 1][j - 1]
            if p[i - 1] == "*" and i > 1:
                # hard part to understand
                if s[j - 1] == p[i - 2] or p[i - 2] == ".":
                # * is not used as empty
                    dp[i][j] = (dp[i - 2][j] or dp[i][j - 1])
                else: # * is used as empty
                    dp[i][j] = dp[i - 2][j]
                
    return dp[-1][-1]

72.Edit Distance

Leetcode: https://leetcode.com/problems/edit-distance/description/

Key:

1
2
3
4
if (str1[i] == str2[j]):
  T[i][j] = T[i-1][j-1]
else:
  T[i][j] = min(T[i-1][j], T[i][j-1], T[i-1][j-1]) {Since this is calculating min distance, we should select a minimum way to calculate next value}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def minDistance(self, word1: str, word2: str) -> int:
    if not word1:
        return len(word2)
    if not word2:
        return len(word1)
    dp = [[0 for _ in range(len(word2))] for _ in range(len(word1))]
    word2Used = False
    word1Used = False
    for j in range(len(word2)):
        if j == 0 and word2[j] != word1[0]:
            dp[0][0] = 1
        elif word1[0] == word2[j] and not word1Used:
            dp[0][j] = dp[0][j - 1]
            word1Used = True
        else:
            dp[0][j] = dp[0][j - 1] + 1
            
    for i in range(1, len(word1)):
        if word2[0] == word1[i] and not word2Used:
            dp[i][0] = dp[i - 1][0]
            word2Used = True
        else:
            dp[i][0] = dp[i - 1][0] + 1
    for i in range(1, len(word1)):
        for j in range(1, len(word2)):
            if word1[i] == word2[j]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
    
    return dp[-1][-1]

44. Wildcard Matching

Leetcode: https://leetcode.com/problems/wildcard-matching/submissions/

Analyze:

1
2
3
4
5
6
7
if "*" -> 
    - if "": dp[i - 1][j]
    - if not "": "*" len = 1: dp[i - 1][j - 1], "*" len > 1: dp[i][j - 1]
if "?" -> 
    - dp[i - 1][j - 1]
if ch -> 
    - if match: dp[i - 1][j - 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def isMatch(self, s: str, p: str) -> bool:
    dp = [[False for j in range(len(s) + 1)] for i in range(len(p) + 1)]
    for i in range(len(p) + 1):
        for j in range(len(s) + 1):
            # initialize
            if i == 0:
                if j == 0:
                    dp[i][j] = True
                else:
                    dp[i][j] = False
            elif j == 0:
                if i > 0:
                    if p[i - 1] == "*" and dp[i - 1][j]:
                        dp[i][j] = True
            else:
                if p[i - 1] == "*":
                    dp[i][j] = (dp[i - 1][j] or dp[i][j - 1] or dp[i - 1][j - 1])
                elif p[i - 1] == "?" or p[i - 1] == s[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
    return dp[-1][-1]

647. Palindromic Substrings

Leetcode: https://leetcode.com/problems/palindromic-substrings/

  • base case: len is 1, dp[i][j] = 1, len is 2, if s[i] == s[j] then dp[i][j] = 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def countSubstrings(self, s: str) -> int:
    # state: dp[i][j] = 1 if s[i:j + 1] is palindrome
    n = len(s)
    dp = [[0 for i in range(n)] for j in range(n)]
    res = 0
    l = 1
    while l <= n:
        i = 0
        while i + l - 1 < n:
            j = i + l - 1
            if i == j:
                dp[i][j] = 1
            elif i + 1 == j and s[i] == s[j]:
                dp[i][j] = 1
            elif dp[i + 1][j - 1] == 1 and s[i] == s[j]:
                dp[i][j] = 1
            res += dp[i][j]
            i += 1
        l += 1
    return res

5. Longest Palindromic Substring

Leetcode: https://leetcode.com/problems/longest-palindromic-substring/

  • Start from l = 1, l = 2 as base cases
  • If dp[i + 1][j - 1] and s[i] == s[j] then s[i: j + 1] is also palindrome
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def longestPalindrome(self, s: str) -> str:
    n = len(s)
    res = ""
    dp = [[False for j in range(n)] for i in range(n)]
    for l in range(n + 1):
        for i in range(n):
            j = i + l - 1
            if j < 0 or j == n:
                break
            if l == 1:
                dp[i][j] = True
                res = max(res, s[i: j + 1], key=len)
            elif l == 2 and s[i] == s[j]:
                dp[i][j] = True
                res = max(res, s[i: j + 1], key=len)
            else:
                if i + 1 < n and j - 1 >= 0 and dp[i + 1][j - 1] and s[i] == s[j]:
                    dp[i][j] = True
                    res = max(res, s[i: j + 1], key=len)
    return res

516. Longest Palindromic Subsequence

  • Palindrom string problem always checks dp[i + 1][j - 1] and s[i] == s[j], if this exists, the longest length from s[i] to s[j] is dp[i + 1][j - 1] + 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestPalindromeSubseq(self, s: str) -> int:
    dp = [[1 for _ in range(len(s))] for _ in range(len(s))]
    for l in range(1, len(s) + 1):
        for i in range(len(s)):
            j = i + l - 1
            if j >= len(s):
                break
            if l == 2 and s[i] == s[j]:
                dp[i][j] = 2
            elif l >= 3:
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][-1]

LIS (Longest Increasing Sequence Problem)

300. Longest Increasing Subsequence

Leetcode: https://leetcode.com/problems/longest-increasing-subsequence/
Video: https://www.youtube.com/watch?v=l2rCz7skAlk

Solution 1: Normal Dynamic Programming O(N^2)

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLIS(self, nums: List[int]) -> int:
    n = len(nums)
    dp = [1 for _ in range(n)]
    dp[0] = 1
    res = 0
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        res = max(dp[i], res)
    return res

Solution 2: Optimized Dynamic Programming with greedy （O(nlogn) (Patience Sorting)

  • dp[i] = the smallest ending number of a subsequence that has length i + 1
  • Init dp = []
  • For each num, we can use it to:
    • Extend the longest subsequence
    • Replace a number to generate a better subsequence
    • Find the smallest last number for the sequence
  • DP array is in acsending order, we can use binary search to find the insertion position

Binary search in dp array:

  1. Use a spare array to store the increasing subsequence (keep it increasing)
  2. For current element, append if it’s greater than the last element of the increasing subsequence, replace it if it’s smaller (keep the subsequence compact so that it can fit more numbers in the future)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums:
        return 0
    maxLen = 1
    dp = [-float('inf') for num in range(len(nums))]
    dp[0] = nums[0]
    i = 1
    while i < len(nums):
        last = dp[maxLen - 1]
        if nums[i] > last:
            dp[maxLen] = nums[i]
            maxLen += 1
        else:
            # bsearch insert point for nums[i]
            l, r = 0, maxLen - 1
            while l < r:
                mid = (l + r) // 2
                if nums[i] > dp[mid]:
                    l = mid + 1
                else:
                    r = mid
            dp[l] = nums[i]
        i += 1
        
    return maxLen

1235. Maximum Profit in Job Scheduling

Leetcode: https://leetcode.com/problems/maximum-profit-in-job-scheduling/

Original DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    # dp[i][j] = max(dp[i][k] + dp[k][j] for k in range(i + 1, j - 1)): maximum value between i:j + 1 time
    # return max(dp[i][j])
    
    n = max(endTime)
    d = collections.defaultdict(collections.defaultdict)
    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    
    for i in range(len(startTime)):
        # print(d[startTime[i]][1], endTime[i])
        d[startTime[i]][endTime[i]] = profit[i]
        dp[startTime[i]][endTime[i]] = d[startTime[i]][endTime[i]]
    
    res = 0
    for i in range(n):
        for l in range(1, n + 1):
            j = i + l - 1
            if j > n:
                continue
            if l == 1:
                dp[i][j] = 0
            else:
                for k in range(i, j):
                    time = 0
                    if j in d[i]:
                        time = d[i][j]
                    dp[i][j] = max(dp[i][j], time, dp[i][k] + dp[k][j])
                    res = max(res, dp[i][j])
    return res

Optimzed DP solutioon: DP + knapsack?

  • Sort by ending time: for each interval: take it (dp[prevEnd] + curProfit) or not dp[arr[i - 1][1]] 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    n = len(profit)
    
    arr = [[startTime[i], endTime[i], profit[i]] for i in range(n)]
    arr.sort(key=lambda x:x[1])
    dp = {} # end: max
    for i in range(n):
        dp[arr[i][1]] = arr[i][2]
    
    def bsearch(target, end):
        l, r = 0, n - 1
        prevIndex = 0
        while l <= r:
            mid = (l + r) // 2
            if target < arr[mid][1]:
                r = mid - 1
            else:
                prevIndex = mid
                l = mid + 1
        return prevIndex
    res = 0
    # binary search for the previous end that smaller or equal to the current start
    for i in range(n):
        curStart, curEnd, curProfit = arr[i]
        prevEndIndex = bsearch(curStart, i)
        prevEnd = arr[prevEndIndex][1]
        if prevEndIndex == 0 and i > 0 and prevEnd > curStart:
            dp[curEnd] = max(curProfit, dp[arr[i - 1][1]])
        elif i > 0:
            # take it or not
            dp[curEnd] = max(dp[prevEnd] + curProfit, dp[arr[i - 1][1]])
        res = max

My DFS solution (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    # make tuples and sort by startTime
    n = len(profit)
    time = [] # []
    for i in range(n):
        time.append((startTime[i], endTime[i], profit[i]))
    time.sort(key = lambda x: x[0])
    
    # construct graph: {(timeIndex, weight): [index startTime >= endTime[timeIndex]]}
    def bsearch(target):
        # search for the smallest startTime that's larger than target
        l, r = 0, n - 1
        while l < r:
            mid = (l + r) // 2
            if time[mid][0] < target:
                l = mid + 1
            else:
                r = mid
        return l
    graph = collections.defaultdict(int)
    indegree = [0 for _ in range(n)]
    
    for i in range(n):
        index = bsearch(time[i][1])
        if time[index][0] >= time[i][1]:
            graph[i] = index
            for i in range(index, n):
                indegree[i] += 1
        else:
            graph[i] = n
    
    queue = []
    for index in range(n):
        if indegree[index] == 0:
            queue.append((index, time[index][2]))
    
    res = 0
    def dfs(index, curWeight):
        nonlocal res
        res = max(res, curWeight)
        for nb in range(graph[index], n):
            dfs(nb, curWeight + time[nb][2])
        return
            
    for start, weight in queue:
        dfs(start, weight)
    
    return res

Similar problem: 1713, 673

1713. Minimum Operations to Make a Subsequence

Leetcode: https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/

Video: https://www.youtube.com/watch?v=5vBPESNPEu4

1
2


673. Number of Longest Increasing Subsequence

leetcode: https://leetcode.com/problems/number-of-longest-increasing-subsequence/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def findNumberOfLIS(self, nums: List[int]) -> int:
    # calculate LIS first
    if not nums:
        return 0
    n = len(nums)
    LIS = [1 for _ in range(n)]
    NLIS = [1 for _ in range(n)]
    
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                if LIS[i] < LIS[j] + 1:
                    LIS[i] = max(LIS[i], LIS[j] + 1)
                    NLIS[i] = NLIS[j]
                elif LIS[i] == LIS[j] + 1:
                    NLIS[i] += NLIS[j]
    maxLen = max(LIS)
    ans = 0
    for i in range(n):
        if LIS[i] == maxLen:
            ans += NLIS[i]
    return ans

Similar problem: 1143. Longest Common Subsequence

1143. Longest Common Subsequence

Leetcode: https://leetcode.com/problems/longest-common-subsequence/

1
2
3
4
5
6
7
8
9
10
11
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    dp = [[0 for _ in range(len(text1) + 1)] for _ in range(len(text2) + 1)]
    for i in range(len(text2) + 1):
        for j in range(len(text1) + 1):
            new_i, new_j = i - 1, j - 1
            if new_i >= 0 and new_j >= 0:
                if text2[new_i] != text1[new_j]:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                else:
                    dp[i][j] = dp[i - 1][j - 1] + 1
    return dp[-1][-1]

354. Russian Doll Envelopes

Leetcode: https://leetcode.com/problems/russian-doll-envelopes/

  • sort increasing in the first dimension
  • also sort decreasing on the second dimension, so two envelopes that are equal in the first dimension can never be in the same increasing subsequence
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
    envelopes.sort(key=lambda x:(x[0], -x[-1]))
    dp = []
    
    for i in range(len(envelopes)):
        w, h = envelopes[i][0], envelopes[i][1]
            # find smallest wi, hi in dp that wi >= w and 
        l, r = 0, len(dp)
        while l < r:
            mid = (l + r) // 2
            if dp[mid][1] < h:
                l = mid + 1
            else:
                r = mid
        # replace
        if l == len(dp):
            dp.append([w, h])
        if l < len(dp):
            dp[l][0] = w
            dp[l][1] = h
    # print(envelopes)
    # print(dp)
    return len(dp)

Jump Problem

403. Frog Jump

Leetcode: https://leetcode.com/problems/frog-jump/description/

Video: https://www.youtube.com/watch?v=oTCPG1ezlKc

[Solution]

  1. Create a dictionary with key representing each stone, value is a set containing the possible next steps
  2. Iterate through stones, keep adding possible next steps into sets when iterating. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def canCross(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        dp = {}
        for stone in stones: # Initialize map
            dp[stone] = set()
        dp[stones[0]].add(1)
        
        for stone in stones: # 0 -> last stone
            nextSteps = dp[stone]
            for step in nextSteps:
                if stone + step in dp:
                    if stone + step == stones[-1]: # Reach to the end
                        return True
                    if step - 1 > 0:
                        dp[stone + step].add(step - 1)
                        
                    dp[stone + step].add(step)
                    dp[stone + step].add(step + 1)
                    
        return False

55. Jump Game

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

Note: Start from the end of the nums, see if I start from i, can I reach to the nearest “good point”. A “good point” is the location where I can reach to the end.

1
2
3
4
5
6
7
8
9
10
def canJump(self, nums: List[int]) -> bool:
    dp = [False] * len(nums)
    near = len(nums) - 1
    dp[-1] = True
    for i in reversed(range(len(nums) - 1)):
        # If you can reach to the nearest good point
        if nums[i] + i >= near:
            dp[i] = True
            near = i
    return dp[0]

91. Decode Ways

Leetcode: https://leetcode.com/problems/decode-ways/

[Solution]

  • use an array dp[] to do memoization
  • Go though s by length 1 and 2
  • Check validation of each elem 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def numDecodings(self, s: 'str') -> 'int':
        dp = [0] * (len(s) + 1)
        dp[0] = 1
        if s[0] == '0':
            dp[1] = 0
        else:
            dp[1] = 1
        for i in range(1, len(s)):
            one = s[i]
            two = s[i - 1: i + 1]

            if one == '0':
                if s[i-1] == '0' or s[i-1] > '2':  
                    return 0
                dp[i + 1] = dp[i - 1]
            else:
                if one > '0' and one <= '9':
                    dp[i + 1] += dp[i]
                if two > '10' and two < '27':
                    dp[i + 1] += dp[i - 1]
        return dp[-1]

583. Delete Operation for Two Strings

Leetcode: https://leetcode.com/problems/delete-operation-for-two-strings/
[Solution]

  • Find the longest common sub sequence (not need to be continued)
  • Construct dp array
  • The last element in the array reprents the final result after deleting characters
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# longest common sequence
#   t o m c a t - 1
# t 1 1 1 1 1 1
# o 1 2 2 2 2 2
# b 1 2 2 2 2 2
# a 1 2 2 2 3 3
# c 1 2 2 3 3 3
# a 1 2 2 3 4 4
# t 1 2 2 3 4 5
# -2
#   s e a -1
# e 0 1 1
# a 0 1 2
# t 0 1 2
# -1
class Solution:
    def minDistance(self, word1: 'str', word2: 'str') -> 'int':
        if len(word1) == 0:
            return len(word2)
        if len(word2) == 0:
            return len(word1)
        dp = []
        for ch in range(len(word2)):
            dp.append([0] * len(word1))
        for i in range(len(word2)):
            for j in range(len(word1)):
                if word2[i] == word1[j]:
                    if i == 0 and j == 0:
                        dp[i][j] = 1
                    elif j == 0:
                        dp[i][j] = 1
                    elif i == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    if i == 0 and j == 0:
                        dp[i][j] = 0
                    elif j == 0:
                        dp[i][j] = dp[i - 1][j]
                    elif i == 0:
                        dp[i][j] = dp[i][j - 1]
                    else:
                        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        return len(word1) - dp[-1][-1] + (len(word2) - dp[-1][-1])

338. Counting Bits

Leetcode: https://leetcode.com/problems/counting-bits/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Solution 1: P(x)=P(x/2)+(xmod2)
def countBits(self, num: int) -> List[int]:
    res = [0] * (num + 1)
    for i in range(num + 1):
        res[i] = res[i >> 1] + (i & 1)
    return res

# Solution 2: P(x)=P(x&(x−1))+1; set the rightmost slot to 0, and plus 1
def countBits(self, num: int) -> List[int]:
    res = [0] * (num + 1)
    for i in range(num + 1):
        res[i] = res[i >> 1] + (i & 1)
    return res

def countBits(self, num: int) -> List[int]:
    if num == 0:
        return [num]
    res = [0] * (num + 1)
    res[1] = 1
    for i in range(2, num + 1):
        if (i - 1) & 1 == 0: # end with 0
            res[i] = res[i - 1] + 1
        else: # end with 1
            res[i] = res[((i - 1) >> 1) + 1]
    return res

312. Burst Balloons

Leetcode: https://leetcode.com/problems/burst-balloons/

Video: https://www.youtube.com/watch?v=z3hu2Be92UA

[Solution]

  • [0,]

Largest area problem

221. Maximal Square

Leetcode: https://leetcode.com/problems/maximal-square/

[Solution]

  • Use a m*n dp matrix
  • Each cell in the dp represents the maximum length of the square when (i, j) is the right bottom corner of the square
  • Transition function: min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maximalSquare(self, matrix: List[List[str]]) -> int:
    dp = []
    if not matrix or len(matrix[0]) == 0:
        return 0
    res = 0
    for row in matrix:
        dp.append([0 for ele in row])
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '0':
                dp[i][j] = 0
            else:
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            res = max(res, dp[i][j])
    return res*res

84. Largest Rectangle in Histogram

Leetcode: https://leetcode.com/problems/largest-rectangle-in-histogram/

85. Maximal Rectangle

Leetcode: https://leetcode.com/problems/maximal-rectangle/

Solution I

  • Store maximum width when current cell is the right bottom corner fo rectangle
  • Go up (row - curRow) * min(maxWidth in the column) is the maximum area when the current cell is the right bottom corner

Time Complexity
O(N^2M). Computing the maximum area for one point takes O(N). There are N * M points.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maximalRectangle(self, matrix: List[List[str]]) -> int:
    maxWidth = [[0 for col in matrix[0]] for row in matrix]
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if j == 0:
                maxWidth[i][j] = int(matrix[i][j])
            else:
                if matrix[i][j] == '1':
                    maxWidth[i][j] = maxWidth[i][j - 1] + 1
    maxArea = 0
    for row in range(len(matrix)):
        for col in range(len(matrix[0])):
            minWidth = maxWidth[row][col]
            for curRow in reversed(range(row + 1)):
                minWidth = min(minWidth, maxWidth[curRow][col])
                area = minWidth * (row - curRow + 1)
                maxArea = max(maxArea, area)
    return maxArea

Solution II

TBA

1277. Count Square Submatrices with All Ones

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def countSquares(self, matrix: List[List[int]]) -> int:
    #  1 1
    #  1 1
    #  square -> expand speed same for x direction and y direction
    #  if matrix[i - 1][j - 1] and matrix[from 0 to i][j] and matrix[i][from 0 to j] -> true (m + n) times
    #  I want to know how many continuous 1 above and left to me
    n, m = len(matrix), len(matrix[0])
    dp = [[[0, 0, 0] for _ in range(m + 1)] for _ in range(n + 1)]
    # dp[i][j] [0] -> with i, j as bottom right corder, how many valid squares
    # dp[i][j] [1] -> how many continuous 1s above
    # dp[i][j] [2] -> how many continuous 1s to the left
    # dp[i][j] is valid if dp[i - 1][j - 1] and dp[i - 1][j][1] == dp[i - 1][j - 1][1] and dp[i][j - 1][2] == dp[i - 1][j - 1][2]
    # start from edge len == 1 to min(m, n)
    l = 1
    res = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if matrix[i - 1][j - 1] == 1:
                if dp[i - 1][j - 1] != 0:
                    dp[i][j][0] = min(dp[i - 1][j - 1][0], dp[i - 1][j][1], dp[i][j - 1][2]) + 1
                else:
                    dp[i][j][0] = 1
                dp[i][j][1] = dp[i - 1][j][1] + 1
                dp[i][j][2] = dp[i][j - 1][2] + 1
            res += dp[i][j][0]
    return res

1048. Longest String Chain

Leetcode: https://leetcode.com/problems/longest-string-chain/

My DFS super long solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class GraphNode:
    def __init__(self, value):
        self.val = value
        self.children = []
        self.indegree = 0
        self.outdegree = 0
        
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key = lambda x: len(x))
        def pred(a, b):
            if len(b) - len(a) != 1:
                return False
            for ch in a:
                if ch not in b:
                    return False
            return True
        graph = {}
        for word in words:
            graph[word] = GraphNode(word)
                
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if (pred(words[i], words[j])):
                    graph[words[i]].children.append(graph[words[j]])
                    graph[words[j]].indegree += 1
                    graph[words[i]].outdegree += 1
                    
        # print(graph)
        res = 0
        stack = []
        for word in graph:
            node = graph[word]
            if node.indegree == 0:
                stack.append([node, 1])
        while stack:
            cur = stack.pop()
            # print(cur)
            res = max(res, cur[1])
            children = cur[0].children
            for child in children:
                stack.append([child, cur[1] + 1])
        return res

DFS + Memoization

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import collections

class Node:
    def __init__(self, word):
        self.word = word
        self.neibs = []
        self.indegree = 0
        
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=lambda x: len(x))
        def isPred(a, b):
            if len(a) + 1 != len(b):
                return False
            for i in range(len(b)):
                if b[:i] + b[i + 1:] == a:
                    return True
            return False
        
        graph = {}
        
        for word in words:
            graph[word] = Node(word)
            
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if isPred(words[i], words[j]):
                    node = graph[words[j]]
                    node.neibs.append(graph[words[i]])
                    graph[words[i]].indegree += 1  
        
        memo = collections.defaultdict(int)
        def dfs(node):
            # return the longest length
            nonlocal memo
            word = node.word
            if word in memo:
                return memo[word]
            
            maxLen = 1
            for neib in graph[word].neibs:
                maxLen = max(maxLen, 1 + dfs(neib))
            memo[word] = maxLen
            return maxLen
        
        res = 0
        for word in graph:
            if graph[word].indegree == 0:
                res = max(res, dfs(graph[word]))
        return res

DP Solution:

TBA

91. Decode Ways

Leetcode: https://leetcode.com/problems/decode-ways/

Need to consider a lot of edge cases with “0”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def numDecodings(self, s: str) -> int:
    dp = [0] * (len(s) + 1)
    if not s or len(s) == 0:
        return 0
    if s[0] != "0":
        dp[0] = 1
    else:
        return 0
    if len(s) > 1:
        dp[1] = 1
    else:
        return 1
    for i in range(2, len(s) + 1):
        j = i - 1
        if "10" < s[j - 1: j + 1] <= "26" and s[j] != "0":
            dp[i] = dp[i - 1] + dp[i - 2]
        elif s[j] == "0" and s[j - 1] >= "3":
            return 0
        elif s[j] == "0":
            if j > 0 and s[j - 1] == "0":
                return 0
            elif j > 1 and "10" < s[j - 2: j] < "26":
                dp[i] = dp[i - 2]
            else:
                dp[i] = dp[i - 1]
        else:
            dp[i] = dp[i - 1]
    return dp[-1]

239. Sliding Window Maximum

Leetcode: https://leetcode.com/problems/sliding-window-maximum/

Solution 1: Use a heap. Time complexity: O(Nlogk)

1
2
3
4
5
6
7
8
9
10
11
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    win = []
    res = []
    for num in nums:
        win.append(-num)
        if len(win) == k:
            heap = win[::]
            heapify(heap)
            res.append(-heappop(heap))
            win.pop(0)
    return res

Solution 2:

  1. Use a deque, popleft() when getting new numbers into window, pop() while incoming number is larger than deque[-1], and then append incoming number at the end of the deque. In this way, deque[0] would always be the largest one.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    if len(nums) == 0 or k == 0:
        return []
    deq = deque()
    def move_window(i):
        if deq and i - deq[0] == k:
            deq.popleft()
        while deq and nums[i] > nums[deq[-1]]:
            deq.pop()
    max_index = 0
    for i in range(k):
        move_window(i)
        deq.append(i)
        if nums[i] > nums[max_index]:
            max_index = i
    res = [nums[max_index]]
    for i in range(k, len(nums)):
        move_window(i)
        deq.append(i)
        res.append(nums[deq[0]])
    return res

Solution 3: Dynamic Programming

  1. Split input array into blocks with length = k
  2. Use two arrays left and right to record the maximum number within the sub-windows
  3. max(right[rightBorder], left[leftBorder])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    if len(nums) == 0 or k == 0:
        return []
    left = [0] * len(nums)
    right = [0] * len(nums)
    right[0] = nums[0]
    left[-1] = nums[-1]
    for i in range(1, len(nums)):
        if i % k == 0:
            right[i] = nums[i]
        else:
            right[i] = max(right[i - 1], nums[i])
        j = len(nums) - i - 1
        if (j + 1) % k == 0 or j == len(nums) - 1:
            left[j] = nums[j]
        else:
            left[j] = max(left[j + 1], nums[j])
        
    res = []
    i = 0
    while i + k - 1 < len(nums):
        res.append(max(right[i + k - 1], left[i]))
        i += 1
    return res

312. Burst Balloons

Leetcode: https://leetcode.com/problems/burst-balloons/

Good Video: https://www.youtube.com/watch?v=Ci39lcoLbyw

Each cell in the dp matrix represents the maximum value we can get using left and right as borders. Within the border, we calculate each cell i in range(left + 1, right) assuming i is the last balloon to burst. And that makes the transition formula as: nums[i] * nums[left] * nums[right] + dp[left][i] + dp[i + 1][right]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def maxCoins(self, nums: List[int]) -> int:
    if not nums:
        return 0
    deq = deque(nums)
    deq.append(1)
    deq.appendleft(1)
    n = len(deq)
    res = 0
    dp = [[0 for j in range(n)] for i in range(n)]
    for l in range(n):
        for left in range(n - l):
            right = left + l
            for i in range(left + 1, right):
                dp[left][right] = max(dp[left][right], deq[i] * deq[left] * deq[right] + dp[left][i] + dp[i][right])
    return dp[0][n - 1]

152. Maximum Product Subarray

Leetcode: https://leetcode.com/problems/maximum-product-subarray/

The key part is to deal with negative values. We use two value max and min to keep track of maximum and minimum product so far, when we meet negative values, we swap them.

1
2
3
4
5
6
7
8
9
10
11
12
13
def maxProduct(self, nums: List[int]) -> int:
    if not nums:
        return 0
    res = mx = mi = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < 0:
            mx, mi = mi, mx
            
        mx = max(nums[i], mx * nums[i])
        mi = min(nums[i], mi * nums[i])
        
        res = max(res, mx)
    return res

198. House Robber

Leetcode: https://leetcode.com/problems/house-robber/

Use mx as a memoization to store the position of the largest value so far.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    mx = [0] * len(nums)
    
    dp[0] = nums[0]
    dp[1] = nums[1]
    
    if dp[1] > dp[0]:
        res = dp[1]
        mx[1] = 1
    else:
        res = dp[0]
        mx[1] = 0
    
    for i in range(2, len(nums)):
        dp[i] = max(nums[i], nums[i] + dp[mx[i - 2]])
        if dp[i] > dp[i - 1]:
            mx[i] = i
        else:
            mx[i] = mx[i - 1]
        res = max(res, dp[i])
    return res

0/1 knapsack problem

0: Don’t pick the item.
1: Pick the item.

Video: https://www.youtube.com/watch?v=8LusJS5-AGo

  1. Initiate DP array of n * capacity: n the number of coins
  2. dp[i][j] = max(not_select(i), select(i)) = max(dp[i - 1][j], dp[][capacity - elements[i]])

322. Coin Change Problem

  • dp[i][j] represents maxim value with coins in coins[:i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [[float('inf') for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
    for i in range(len(coins) + 1):
        for j in range(amount + 1):
            if i == 0 and j == 0:
                dp[i][j] = 0
            elif i == 0:
                dp[i][j] = -1
            elif j == 0:
                dp[i][j] = 0
            else:
                if j < coins[i - 1]:
                    dp[i][j] = dp[i - 1][j]
                    # print(i, j)
                else:
                    if dp[i - 1][j] != -1 and dp[i][j - coins[i - 1]] != -1:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
                    elif dp[i][j - coins[i - 1]] == -1:
                        dp[i][j] = dp[i - 1][j]
                    elif dp[i - 1][j] == -1:
                        # print(i, j)
                        dp[i][j] = dp[i][j - coins[i - 1]] + 1
                    else:
                        dp[i][j] = -1
    if dp[-1][-1] == float('inf'):
        return -1
    return dp[-1][-1]

416. Partition Equal Subset Sum

Leetcode: https://leetcode.com/problems/partition-equal-subset-sum/

Solution: If there exists some combinations of the set that sums to total // 2, which means the left elements in the array can also sum up to total // 2, then return true.
d[i][j] meas whether the specific sum j can be gotten from the first i numbers.

DP Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2 == 1:
        return False
    dp = [[0 for j in range(total // 2 + 1)] for i in range(len(nums) + 1)]
    for i in range(len(nums) + 1):
        for j in range(total // 2 + 1):
            if j == 0:
                dp[i][j] = 1
            elif i > 0 and j - nums[i - 1] >= 0:
                dp[i][j] = dp[i - 1][j]  or dp[i - 1][j - nums[i - 1]]    
    if dp[-1][-1] == 1:
        return True
    return False

Hash table + memo solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total & 1 == 1:
            return False
        self.memo = {}
        total //= 2
        return self.helper(total, 0, nums)
    
    def helper(self, total, index, nums):
        if total == 0:
            return True
        if total < 0 or index == len(nums):
            return False
        if (index, total) in self.memo: # If used this combination before
            return self.memo[(index, total)]
        self.memo[(index, total)] = self.helper(total - nums[index], index + 1, nums) or self.helper(total, index + 1, nums) # Select nums[index] or not select nums[index]
        return self.memo[(index, total)]

474. Ones and Zeroes

Leetcode: https://leetcode.com/problems/ones-and-zeroes/

Video: https://www.youtube.com/watch?v=R-U_pY0OBKI&t=655s&ab_channel=HuifengGuan

  • dp[i][j] 用i个1和j个0最多能装多少个元素
  • Go through the strs array, process strings one by one
  • Update DP array from the end to avoid unintended overriding
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
    dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
    
    for s in strs:
        ones, zeros = 0, 0
        for ch in s:
            if ch == "1":
                ones += 1
            else:
                zeros += 1
        
        for i in reversed(range(ones, n + 1)):
            for j in reversed(range(zeros, m+1)):
                dp[i][j] = max(dp[i][j], dp[i - ones][j - zeros] + 1)
                
    return dp[-1][-1]

518. Coin Change 2

Leetcode: https://leetcode.com/problems/coin-change-2/

dp[i][j]: j is amount, i is current coins. dp[i][j] is the sum of select current coin + not select current coin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def change(self, amount: int, coins: List[int]) -> int:
    dp = [[0 for _ in range(amount + 1)] for _ in range(len(coins) + 1)]
    for i in range(len(coins) + 1):
        for j in range(amount + 1):
            if j == 0:
                dp[i][j] = 1
            elif i == 0:
                dp[i][j] = 0
            else:
                if j >= coins[i - 1]:
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
                else:
                    dp[i][j] = dp[i - 1][j]
    return dp[-1][-1]

Optimize to space O(n):

1
2
3
4
5
6
7
8
def change(self, amount: int, coins: List[int]) -> int:
    dp = [1] + [0] * amount
    for i in range(1, len(coins) + 1):
        for j in range(1, amount + 1):
            coin = coins[i - 1]
            if j - coin >= 0:
                dp[j] += dp[j - coin]
    return dp[-1]

1090. Largest Values From Labels

983. Minimum Cost For Tickets

Leetcode: https://leetcode.com/problems/minimum-cost-for-tickets/

  • Each ticket’s minimum price is only dependent on the previous potential start of ticket period
1
2
3
4
5
6
7
8
9
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
    dp = [0 for _ in range(days[-1] + 1)]
    days = set(days)
    for i in range(len(dp)):
        if i in days:
            dp[i] = min(dp[max(0, i - 1)] + costs[0], dp[max(0, i - 7)] + costs[1], dp[max(0, i - 30)] + costs[2])
        else:
            dp[i] = dp[i - 1]
    return dp[-1]

32. Longest Valid Parentheses

Leetcode: https://leetcode.com/problems/longest-valid-parentheses/

See stack solution at leetcode-stack chapter

  • dp[i]: the longest valid substring ending at s[i]: thus all ( is zero
  • For each ), we look at the previous i-1 element, if it’s ( then dp[i] = dp[i - 2] + 2, else if it’s ), then we find the length of the valid substring ending at i - 1: dp[i - 1], and find what’s before this previous valid string, if it’s (, then dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2, else it’s 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestValidParentheses(self, s: str) -> int:
    if not s:
        return 0
    res = 0
    dp = [0 for i in range(len(s))]
    for i in range(1, len(s)):
        if s[i] == ")":
            if s[i - 1] == "(":
                dp[i] = dp[i - 2] + 2
            else:
                if i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2
        res = max(res, dp[i])
    return res

1423. Maximum Points You Can Obtain from Cards

Leetcode: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/

Brute force: try every possibility (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def maxScore(self, cardPoints: List[int], k: int) -> int:
    res = 0
    if k == len(cardPoints):
        return sum(cardPoints)
    if k == 1:
        return max(cardPoints[0], cardPoints[-1])
    
    def helper(leftIndex, rightIndex, curSum, step):
        nonlocal res
        if step == 0:
            res = max(res, curSum)
            return
        helper(leftIndex + 1, rightIndex, curSum + cardPoints[leftIndex], step - 1)
        helper(leftIndex, rightIndex - 1, curSum + cardPoints[rightIndex], step - 1)
    helper(0, len(cardPoints) - 1, 0, k)
    return res

Save sums from 2 directions in 2 arrays and use 2 pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxScore(self, cardPoints: List[int], k: int) -> int:
    sumsLTR = [point for point in cardPoints]
    sumsRTL = [point for point in cardPoints]
    for i in range(1, len(cardPoints)):
        sumsLTR[i] += sumsLTR[i - 1]
    i = len(cardPoints) - 2
    while i >= 0:
        sumsRTL[i] += sumsRTL[i + 1]
        i -= 1
    i = -1
    j = len(cardPoints) - k
    res = 0
    while i <= k - 1:
        if i == -1:
            res = max(res, sumsRTL[j])
        elif j == len(cardPoints):
            res = max(res, sumsLTR[i])
        else:
            res = max(res, sumsRTL[j] + sumsLTR[i])
        i += 1 
        j += 1
    return res

Non-traditional DP

264. Ugly Number II

Leetcode: https://leetcode.com/problems/ugly-number-ii/

Solution: We have an array k of first n ugly number. We only know, at the beginning, the first one, which is 1. Then

1
2
k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2's pointer to 1. Then we test:
k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nthUglyNumber(self, n: int) -> int:
    if n == 1:
        return 1
    dp = [1] * n
    t2, t3, t5 = 0, 0, 0
    for i in range(1, n):
        dp[i] = min(min(dp[t2] * 2, dp[t3] * 3), dp[t5] * 5)
        if dp[i] == dp[t2] * 2:
            t2 += 1
        if dp[i] == dp[t3] * 3:
            t3 += 1
        if dp[i] == dp[t5] * 5:
            t5 += 1
    return dp[-1]

Stock Problems

309. Best Time to Buy and Sell Stock with Cooldown

Leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

Video: https://www.youtube.com/watch?v=oL6mRyTn56M

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxProfit = function(prices) {
    if (prices.length < 2) { return 0 }
    let buy = -prices[0];
    let sell = 0;
    let prevBuy = 0;
    let prevSell = 0;
    let res = buy;
    for (let i = 1; i < prices.length; i++) {
        prevBuy = buy;
        buy = Math.max(prevSell - prices[i],  prevBuy);
        prevSell = sell;
        sell = Math.max(prevBuy + prices[i],  prevSell);
        res = Math.max(res, sell, buy);
    }
    return res;
};

410. Split Array Largest Sum

Leetcode: https://leetcode.com/problems/split-array-largest-sum/
Video: https://www.youtube.com/watch?v=_k-Jb4b7b_0

  • non-aftereffect property: Once the state of a certain stage is determined, it is not affected by the state in the future. In this problem, if we get the largest subarray sum for splitting nums[0...i] into j parts, this value will not affected by how we split the remaining part of numbers
  • dp[i][j] i: num of groups, j: up to nums[:j]
  • Need to visit every 0 <= k < j to get the minimal possible value:dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sum(nums[k + 1: j + 1])))

DP solution (TLE) O(mn^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def splitArray(self, nums, m):
    dp = [[float('inf') for j in range(len(nums))] for i in range(m)]
    dp[0][0] = nums[0]
    for i in range(m):
        for j in range(i, len(nums)):
            if i == 0 and j > 0:
                dp[i][j] = dp[i][j - 1] + nums[j]
                continue
            if i == j:
                dp[i][j] = max(nums[:j + 1])
                continue
            if i > j:
                continue
            for k in range(j):
                dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sum(nums[k + 1: j + 1])))
    return dp[-1][-1]

Recursive solution with memoization (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def splitArray(self, nums: List[int], m: int) -> int:
    dp = [[float('inf') for j in range(len(nums))] for i in range(m + 1)]
    dp[0][0] = nums[0]
    
    _sums = [0 for i in range(len(nums))]
    _sums[0] = nums[0]
    for i in range(1, len(nums)):
        _sums[i] = _sums[i - 1] + nums[i]
    
    def getSmallestSubarraySum(k, m):
        # k: num of groups
        # m: nums[0] ~ nums[m]
        nonlocal dp
        if dp[k][m] != float('inf'):
            return dp[k][m]
        if k > m + 1:
            return float('inf')
        if k == m + 1:
            return max(nums[:m + 1])
        if k == 1:
            return _sums[m]
        ans = float('inf')
        for i in range(m):
            ans = min(ans, max(getSmallestSubarraySum(k - 1, i), _sums[m] - _sums[i]))
        dp[k][m] = ans
        return ans
    return getSmallestSubarraySum(m, len(nums) - 1)

Binary search solution: see binary search page

1139. Largest 1-Bordered Square

Leetcode: https://leetcode.com/problems/largest-1-bordered-square/

Note:

  • dp array is a 2-dimension array, each cell is also an array [left, up], storing the count of continuous 1s to the left of the current cell and to the up of the current cell
  • Then we start traversing the grid, if grid[i][j] == 1
    • from edge l = 1, we get the four corners of the current square
    • !! Remember to check if the left-up corner is also 1
    • We calculate if the increasing of 1s between two corner matches our current l
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def largest1BorderedSquare(self, grid):
    dp = [[[0, 0] for j in range(len(grid[i]))] for i in range(len(grid))] # [left, up]
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if i == 0 and j == 0:
                if grid[i][j] == 1:
                    dp[i][j][0], dp[i][j][1] = 1, 1
            elif i == 0:
                if grid[i][j] == 1:
                    dp[i][j][0], dp[i][j][1] = dp[i][j - 1][0] + 1, 1
            elif j == 0:
                if grid[i][j] == 1:
                    dp[i][j][0], dp[i][j][1] = 1, dp[i - 1][j][1] + 1
            else:
                if grid[i][j] == 1:
                    dp[i][j][0], dp[i][j][1] = dp[i][j - 1][0] + 1, dp[i - 1][j][1] + 1
    res = 0
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            cur = dp[i][j]
            if grid[i][j] != 0:
                for l in range(1, min(i + 2, j + 2)):
                    top_left, top_right, bottom_left = dp[i - l + 1][j - l + 1], dp[i - l + 1][j], dp[i][j - l + 1]
                    if sum(top_left) == 0:
                        continue
                    if top_left[0] + l - 1 == top_right[0] and top_left[1] + l - 1 == bottom_left[1] and bottom_left[0] + l - 1 == cur[0] and top_right[1] + l - 1 == cur[1]:
                        res = max(res, l ** 2)
    return res