Keynotes

• to find the max/min value
  • longest increasing subsequence
  • minimum edit distance
• three components
  • repeated sub-problem
  • best sub-structure
  • status change formula

Problems

• longest palindromic substring
• longest valid parentheses
• trapping rain water
• maximum subarray
• unique paths
• unique paths II
• minimum path sum
• climbing stairs
• decode ways
• unique BSTs II
• unique BSTs
• interleaving string
• triangle
• best time to buy and sell stock
• palindrome partitioning
• maximum product subarray
• dungeon game
• house robber
• house robber II
• ugly number II
• perfect squares
• longest increasing subsequence
• range sum query - immutable
• range sum query 2D - immutable
• best time to buy and sell stock with cooldown
• coin change
• house robber III
• counting bits
• integer break
• russian doll envelopes
• count numbers with unique digits
• largest divisible subset
• wiggle subsequence
• combination sum IV
• is subsequence
• split array larget sum
• arithmetic slices
• partition equal subset sum
• ones and zeroes
• target sum
• continuous subarray sum
• shopping offers
• palingromic substrings
• best time to buy and sell stock with transaction fee
• maximum length of repeated subarray
• min cost climbing stairs
• push dominoes
• stone game
• super egg drop
• bitwise ORs of subarrays
• number of music playlists
• binary tree cameras
• longest turbulent subarray
• divisor game
• longest string chain
• last stone weight II
• number of submatrices that sum to target
• filling bookcase shelves
• longest common subsequence
• maximum profit in job scheduling
• maximum points you can obtain from cards
• cherry pickup II
• count sorted vowel strings
• minimum jumps to reach home
• distribute repeating integers
• maxmize grid happiness
• ways to make a fair array
• stone game VII
• maximum height by stacking cubolds

Solutions

Fibonacci

 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

class Solution:
  # brute force with recursion
  def fib_1(self, n: int) -> int:
    if n == 1 or n == 2:
      return 1
    return self.fib_1(n-1) + self.fib_1(n-2)

  # with memo
  def fib_2(self, n: int) -> int:
    if n < 1:
      return 0
    memo = [0] * (n+1)
    def helper(memo, k):
      if k == 1 or k == 2:
        return 1
      if memo[k] != 0:
        return memo[k]
      memo[k] = helper(memo, k-1) + helper(memo, k-2)
      return memo[k]
    return helper(memo, n)

  # with dp table
  def fib_3(self, n: int) -> int:
    dp = [0] * (n+1)
    dp[1] = dp[2] = 1
    for i in range(3, n+1):
      dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

  # with constant memory
  def fib_4(self, n: int) -> int:
    if n == 1 or n == 2:
      return 1
    pre = cur = 1
    for i in range(3, n+1):
      sum_ = pre + cur
      pre = cur
      cur = sum_
    return cur

Coin Change

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
  def coin_change(self, coins: List[int], target: int) -> int:
    dp = [target+1] * (target+1)
    dp[0] = 0
    for i in range(len(dp)):
      for c in coins:
        if (i - coin) < 0:
          continue
        dp[i] = min(dp[i], 1+dp[i-coin])
    if dp[target] == target+1:
      return -1
    return dp[target]

Odd Even Jump

• use TreeMap to find next great/less number
• use two array to simulate the dp array, bottom to top solution

1
2
3
4

class Solution {
    public int oddEvenJumps(int[] arr) {
    }
}