吹拉弹唱


  • Home
  • Archive
  • Categories
  • Tags
  • Books
  •  

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo

Code - Dynamic Programming

Posted at 2022-05-05Updated at 2022-05-05 interview  interview algorithm 

  • Principles
  • Problems
    • Knapsack Problem
      • 0-1 Knapsack
      • Complete Knapsack
    • Interval DP
      • Palindrome
    • Two Strings
      • Matching
    • Histogram
    • Subarray
      • Maximum sum
      • Stock
      • Robber
    • Combination
    • Path/DFS
    • Divide & Conquer
    • Jump Game
  • LeetCode
    • 53. Maximum Subarray
    • 121. Best Time to Buy and Sell Stock
    • 122. Best Time to Buy and Sell Stock II
    • 5. Longest Palindromic Substring
    • 647. Palindromic Substrings
    • 516. Longest Palindromic Subsequence
    • 10. Regular Expression Matching
    • 42. Trapping Rain Water
    • 44. Wildcard Matching
    • 55. Jump Game
    • 45. Jump Game II
    • 1306. Jump Game III
    • 1871. Jump Game VII
    • 1345. Jump Game IV
    • 62. Unique Paths
    • 63. Unique Paths II
    • 64. Minimum Path Sum
    • 70. Climbing Stairs
    • 746. Min Cost Climbing Stairs
    • 72. Edit Distance
    • 85. Maximal Rectangle
    • 84. Largest Rectangle in Histogram
    • 87. Scramble String
    • 312. Burst Balloons
    • 1246. Palindrome Removal
    • 322. Coin Change
    • 518. Coin Change 2
    • 416. Partition Equal Subset Sum
    • 96. Unique Binary Search Trees
    • 91. Decode Ways
    • 639. Decode Ways II
    • 97. Interleaving String
    • 115. Distinct Subsequences
    • 118. Pascal’s Triangle
    • 119. Pascal’s Triangle II
    • 120. Triangle
    • 123. Best Time to Buy and Sell Stock III
    • 188. Best Time to Buy and Sell Stock IV
    • 309. Best Time to Buy and Sell Stock with Cooldown
    • 131. Palindrome Partitioning
    • 132. Palindrome Partitioning II
    • 1278. Palindrome Partitioning III
    • 1745. Palindrome Partitioning IV
    • 139. Word Break
    • 140. Word Break II
    • 472. Concatenated Words
    • 152. Maximum Product Subarray
    • 174. Dungeon Game
    • 198. House Robber
    • 213. House Robber II
    • 221. Maximal Square
    • 233. Number of Digit One
    • 263. Ugly Number
    • 264. Ugly Number II
    • 313. Super Ugly Number
    • 1201. Ugly Number III
    • 279. Perfect Squares
    • 204. Count Primes
    • 300. Longest Increasing Subsequence

# Principles

  1. Determine the dp array (dp table) and the meaning of the subscript
  2. Determine the recurrence formula
  3. How to initialize the dp array
  4. Determine the traversal order
  5. Derive the dp array by example

# Problems

# Knapsack Problem

# 0-1 Knapsack

416. Partition Equal Subset Sum Valid.

# Complete Knapsack

322. Coin Change Minimum weight.
518. Coin Change 2 Total Number

# Interval DP

# Palindrome

1
2
3
4
5
6
7
for i := N - 1; i >= 0; i-- {
    for j := i; j < N; j++ {
        if s[i] == s[j] {

        }
    }
}

5. Longest Palindromic Substring Check if valid. Contiguous.
647. Palindromic Substrings Find the number of all possible combinations. Contiguous.
516. Longest Palindromic Subsequence Find the length of longest subsequence. Not contiguous.

# Two Strings

# Matching

10. Regular Expression Matching Matching. Valid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for i := 1; i < S + 1; i++ {
    for j := 1; j < P + 1; j++ {
        if j < P && p[j] == '*' {
            // skip if this character is followed by *
            continue
        } else if p[j-1] == '*' {
            dp[i][j] = dp[i][j - 2]
            if p[j-2] == '.' || s[i-1] == p[j-2] {
                dp[i][j] = dp[i][j] || dp[i-1][j-2] || dp[i-1][j]
            }
        } else if p[j-1] == '.' || s[i-1] == p[j-1] {
                dp[i][j] = dp[i-1][j-1]
        }
    }
}

44. Wildcard Matching Matching. Valid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dp[0][0] = true
for j := 1; j < P+1; j++ {
    if p[j-1] == '*' {
        dp[0][j] = dp[0][j-1]
    }
}

for i := 1; i < S+1; i++ {
    for j := 1; j < P+1; j++ {
        if p[j-1] == '*' {
            dp[i][j] = dp[i][j-1] || dp[i-1][j]
        } else if p[j-1] == '?' || s[i-1] == p[j-1] {
            dp[i][j] = dp[i-1][j-1]
        }
    }
}

72. Edit Distance

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for i := 0; i < m+1; i++ {
    dp[i][0] = i
}
for j := 0; j < n+1; j++ {
    dp[0][j] = j
}
for i := 1; i < m+1; i++ {
    for j := 1; j < n+1; j++ {
        if word1[i - 1] == word2[j - 1] {
            dp[i][j] = dp[i - 1][j - 1]
        } else {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
        }
    }
}

# Histogram

42. Trapping Rain Water. Area. Bidirectional Search. DP(Memorized Search). Two pointer. Monolithic Stack.
84. Largest Rectangle in Histogram. Area. Bidirectional Search. DP(Memorized Search). Monolithic Stack.
85. Maximal Rectangle. Area. Based on 84 for each Row. DP(Memorized Search based on last row).

# Subarray

# Maximum sum

53. Maximum Subarray

# Stock

State Machine/Recursive Formula

121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III

1
2
3
4
5
6
7
8
9
10
11
s0 Idle0 <- Idle0
s1 Hold0 <- s0 Idle0, Hold0
s2 Idle1 <- s1 Hold0, s2 Idle1
s3 Hold2 <- s2 Idle1, s3 Hold2
s4 Idle3 <- s3 Hold2, s4 Idle3

s[0][i] = s[0][i-1]
s[1][i] = max(s[0][i-1] - prices[i], s[1][i-1])
s[2][i] = max(s[1][i-1] + prices[i], s[2][i-1])
s[3][i] = max(s[2][i-1] - prices[i], s[3][i-1])
s[4][i] = max(s[3][i-1] + prices[i], s[4][i-1])

188. Best Time to Buy and Sell Stock IV

1
2
3
4
for int j = 0; j < 2 * k - 1; j += 2 {
    dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i])
    dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i])
}

309. Best Time to Buy and Sell Stock with Cooldown

1
2
3
s[0][i] = max(s[0][i-1], s[2][i-1])
s[1][i] = max(s[1][i-1], s[0][i-1] - prices[i])
s[2][i] = s[1][i-1] + prices[i]

# Robber

State Machine

198. House Robber
213. House Robber II

# Combination

62. Unique Paths Combinatorial number. DP.
63. Unique Paths II With Obstacle.
70. Climbing Stairs 1 or 2 steps. What if 1…N Steps. Find all combinations.
746. Min Cost Climbing Stairs Options with cost. Find the minimum cost.

# Path/DFS

64. Minimum Path Sum Find the minimum path.
87. Scramble String Check path valid.
174. Dungeon Game Backtrack

# Divide & Conquer

312. Burst Balloons
1246. Palindrome Removal

# Jump Game

55. Jump Game
45. Jump Game II
1306. Jump Game III BFS
1345. Jump Game IV BFS cached iterative

# LeetCode

# 53. Maximum Subarray

leetcode

A general dp solution.

The question is quite clear. I only need to return the maximum sum rather the specific subarray.
The first method comes into my mind is the dynamic programming. The maximum sum of the subarray with the index from 0 to N - 1, in which N is the length of the input array, is the larger one between the sum of the subarray with the index between 0 to N-2 adding the N-1 th element, and the N-1 th element which means reset the sum. So we can find the maximum sum of the subarray during the iteration.

Therefore, we can determine the dp array which means the maximum sum of the subarray between the index 0 to subscript i.
And the recurrence formula is:

1
dp[i] = max(nums[i], dp[i - 1] + nums[i])

And initializing the dp array. The dp[0] means the maximum array from 0 to 0, which exactly is nums[0].
The traversal order is incremental.
And manually validate our assumptions with an example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxSubArray(nums []int) int {
    N := len(nums)
    dp := make([]int, N)
    dp[0] = nums[0]
    result := dp[0]
    for i := 1; i < N; i++ {
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
        if (dp[i] > result) {
            result = dp[i]
        }
    }
    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

A greedy solution
We keep a sum of the contiguous subarray adding each new element. Once the sum is less than 0, we reset the sum to 0. Any negative number could reduces the sum, and if the sum is already negative, we’re choosing the large one between the sum of the contiguous subarray and the next element, or simply the next element. The larger one must be the later, which is exactly resetting the sum to 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxSubArray(nums []int) int {
    sum := 0
    max := math.MinInt64
    for _, num := range nums {
        sum += num
        if sum > max {
            max = sum
        }
        if sum < 0 {
            sum = 0
        }
    }
    return max
}

# 121. Best Time to Buy and Sell Stock

leetcode

Greedy Solution

The constraint is I have to sell the stock in a day after buying. So the first method could be finding the minimum value from the left and the maximum value from the right. And the difference between these two numbers is the maximum profit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxProfit(prices []int) int {
    profit := 0
    low := math.MaxInt64
    for _, price := range prices {
        low = min(low, price)
        profit = max(profit, price - low)
    }
    return profit
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

optimized

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func maxProfit(prices []int) int {
    profit := 0
    low := prices[0]
    for _, price := range prices {
        if price < low {
            low = price
        }
        if profit < price - low {
            profit = price - low
        }
    }
    return profit
}

# 122. Best Time to Buy and Sell Stock II

leetcode

Greedy Solution

Since we could only hold one share of stock and we can buy and sell at any time, so we could break the profit down to a single day, and we only count the days which have a positive profit.

1
2
3
4
5
6
7
8
9
func maxProfit(prices []int) int {
    profit := 0
    for i := 1; i < len(prices); i++ {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1]
        }
    }
    return profit
}

# 5. Longest Palindromic Substring

leetcode

DP

Is the substring contiguous? Yes
If multiple substrings are found, which one should I return? Any of them.

The solution I may have a try is dynamic programming.
First, determine the meaning of dp table dp[i][j], which means is the substring from the subscript i to j is palindromic. i is less then j. The interval is left closed and right closed.
Second, determine the recursive formula. If s[i] and s[j] are not equal, there is no chance the substring could be palindromic. Therefore, we discuss the details where s[i] and s[j] are equal. There are 3 situations.

  1. If i == j, then the substring is a letter, so it must be palindromic.
  2. If j - i == 1, then the substring is like ‘aa’, so it is palindromic.
  3. If j - i > 1, then the substring is depending on dp[i+1][j-1].
    Third, determine how to initialize the dp table. dp[0][0] is palindromic, initialize all other elements to false.
    Fourth, determine the traversal order.
    dp[i + 1][j - 1] is at the bottom left of dp[i][j], so dp[i + 1][j - 1] must be determined before dp[i][j]. So it must be traversed from bottom to top and left to right, so as to ensure that dp[i + 1][j - 1] is calculated.
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
func longestPalindrome(s string) string {
    N := len(s)
    dp := make([][]bool, N)
    for i := 0; i < N; i++ {
        dp[i] = make([]bool, N)
    }
    left := 0
    right := 0
    max := 0
    for i := N - 1; i >= 0; i-- {
        for j := i; j < N; j++ {
            if (s[i] == s[j]) {
                if j - i <= 1 {
                    dp[i][j] = true
                } else if (dp[i + 1][j - 1]) {
                    dp[i][j] = true
                }
                if dp[i][j] {
                    if j - i + 1 > max {
                        max = j - i + 1
                        left = i
                        right = j
                    }
                }
            }
        }
    }

    return s[left:right + 1]
}

# 647. Palindromic Substrings

leetcode

This is similar to 5.

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func countSubstrings(s string) int {
    N := len(s)
    dp := make([][]bool, N)
    for i := 0; i < N; i++ {
        dp[i] = make([]bool, N)
    }
    result := 0
    for i := N - 1; i >= 0; i-- {
        for j := i; j < N; j++ {
            if (s[i] == s[j]) {
                if j - i <= 1 {
                    dp[i][j] = true
                } else if (dp[i + 1][j - 1]) {
                    dp[i][j] = true
                }
                if dp[i][j] {
                    result++
                }
            }
        }
    }

    return result
}

# 516. Longest Palindromic Subsequence

leetcode

This is quite similar to 5 other than the situation analysis.
First, determine the meaning of dp table dp[i][j], which means the length of the longest palindromic subsequence from subscript i to j.
Second, determine the recursive formula. If s[i] == s[j], then dp[i][j] = dp[i + 1][j - 1] + 2. If s[i] != s[j], it means that adding s[i] and s[j] at the same time cannot increase the length of the palindrome substring in the interval [i, j], then add s[i] and s respectively. [j] See which one can form the longest palindromic subsequence. The dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
Third, initialize the dp array. dp[i][i] = 1.
Fourth, determine the traversal order. dp[i][j] is dependent on dp[i + 1][j - 1] and dp[i + 1][j] and dp[i][j - 1]. So it must be traversed from bottom to top and left to right.

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
func longestPalindromeSubseq(s string) int {
    N := len(s)
    dp := make([][]int, N)
    for i := 0; i < N; i++ {
        dp[i] = make([]int, N)
        dp[i][i] = 1
    }
    for i := N - 1; i >= 0; i-- {
        for j := i + 1; j < N; j++ {
            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][N-1]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 10. Regular Expression Matching

leetcode

Simply converted to a dp problem.
First, determine the dp table, dp[i][j] means is p[0:j-1] matches s[0:i-1].
Second, determine the recursive formula.

  1. If current p (p[j - 1]) is star, dp[i][j] compares s[i-1] and p[i-1]
  2. because * means matching 0 or more, dp[i][j] at least equals to dp[i][j-2], which ignores the last two characters of p.
  3. If p[i-2] is dot, then the condition is relax to dp[i - 1][j - 2].
  4. And if s[i-1] == p[j - 2], current s equals last p, then dp[i][j] = dp[i - 1][j], check if we remove the last character of s, if the rest of s matches p.
  5. If current p is dot, which could match any character, dp[i][j] = dp[i - 1][j - 1], if the shorter substring matches, then current substring matches.
  6. If current p equals to current s, dp[i][j] = dp[i - 1][j - 1], if the shorter substring matches, then current substring matches.
  7. One optimization is if the next character is star, just skip the current comparison.

Third initialize the dp table.
dp[0][0] must be true.
Matches the 0-length s with p.

Determine the traversal order. From left to right, bottom to up.

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
func isMatch(s string, p string) bool {
    S, P := len(s), len(p)
    dp := make([][]bool, S + 1)
    for i := 0; i < S + 1; i++ {
        dp[i] = make([]bool, P + 1)
    }
    dp[0][0] = true
    
    for j := 1; j < P + 1; j++ {
        if p[j - 1] == '*' {
            dp[0][j] = dp[0][j-2]
        }
    }
        
    
    for i := 1; i < S + 1; i++ {
        for j := 1; j < P + 1; j++ {
            if j < P && p[j] == '*' {
                // skip if this character is followed by *
                continue
            } else if p[j-1] == '*' {
                dp[i][j] = dp[i][j - 2]
                if p[j-2] == '.' || s[i-1] == p[j-2] {
                    dp[i][j] = dp[i][j] || dp[i-1][j-2] || dp[i-1][j]
                }
            } else if p[j-1] == '.' || s[i-1] == p[j-1] {
                    dp[i][j] = dp[i-1][j-1]
            }
        }
    }
    return dp[S][P]
}

# 42. Trapping Rain Water

leetcode

Column Searching

The main idea is to find the maximum wall from the target column i. The first and the last wall do not count.

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
func trap(height []int) int {
    sum := 0
    N := len(height)
    for i := 0; i < N; i++ {
        if i == 0 || i == N - 1 {
            continue
        }
        left := height[i]
        right := height[i]
        for r := i + 1; r < N; r++ {
            if height[r] > right {
                right = height[r]
            }
        }
        for l := i - 1; l >= 0; l-- {
            if height[l] > left {
                left = height[l]
            }
        }
        sum += min(left, right) - height[i]
    }
    return sum
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

Dynamic Programming

Use an array to store the max height.
maxLeft[i] = max(height[i], maxLeft[i - 1]);
maxRight[i] = max(height[i], maxRight[i + 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
33
34
35
36
func trap(height []int) int {
    if len(height) < 2 {
        return 0
    }
    sum := 0
    N := len(height)
    maxLeft := make([]int, N)
    maxRight := make([]int, N)
    maxLeft[0] = height[0]
    maxRight[N-1] = height[N-1]
    for i := 1; i < N; i++ {
        maxLeft[i] = max(maxLeft[i-1], height[i])
    }
    for i := N - 2; i >= 0; i-- {
        maxRight[i] = max(maxRight[i + 1], height[i])
    }
    
    for i := 0; i < N; i++ {
        sum += min(maxLeft[i], maxRight[i]) - height[i]
    }
    return sum
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Double Pointer

Optimization to 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
func trap(height []int) int {
    ans := 0
    left, right := 0, len(height)-1
    leftMax, rightMax := 0, 0
    for left < right {
        leftMax = max(leftMax, height[left])
        rightMax = max(rightMax, height[right])
        if height[left] < height[right] {
            ans += leftMax - height[left]
            left++
        } else {
            ans += rightMax - height[right]
            right--
        }
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 44. Wildcard Matching

leetcode

This is similar to 10 but simpler because the wildcard character are not combined.
Consider it as a dp problem.
First determine the dp table, dp[i][j] means whether p[i-1] can match s[i-1].

  1. If current p[i-1] is star, then dp[i][j] compares s[i-1] and p[j-1].
  2. star matches 0 or more characters. dp[i][j] at least equals to dp[i][j-1], which ignores the last characters of p or dp[i][j] equals to dp[i-1][j], which ignores the last character of s.
  3. If current p[i-1] is dot, which matches any single character. dp[i][j] = dp[i-1][j-1].
  4. If current p[i-1] equals s[i-1], which matches any single character. dp[i][j] = 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
21
22
23
24
func isMatch(s string, p string) bool {
    S, P := len(s), len(p)
    dp := make([][]bool, S+1)
    for i := 0; i < S+1; i++ {
        dp[i] = make([]bool, P+1)
    }
    dp[0][0] = true
    for j := 1; j < P+1; j++ {
        if p[j-1] == '*' {
            dp[0][j] = dp[0][j-1]
        }
    }
    
    for i := 1; i < S+1; i++ {
        for j := 1; j < P+1; j++ {
            if p[j-1] == '*' {
                dp[i][j] = dp[i][j-1] || dp[i-1][j]
            } else if p[j-1] == '?' || s[i-1] == p[j-1] {
                dp[i][j] = dp[i-1][j-1]
            }
        }
    }
    return dp[S][P]
}

# 55. Jump Game

leetcode

Greedy
Let’s say the range of current jump is [curBegin, curEnd], curFarthest is the farthest point that all points is [curBegin, curEnd] can reach. Once the current point reaches curEnd, then trigger another jump and set the new curEnd with curFarthest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func canJump(nums []int) bool {
    if len(nums) == 1 {
        return true
    }
    curEnd, curFarthest := 0, 0
    for i := 0; i < len(nums) - 1; i++ {
        if i + nums[i] > curFarthest {
            curFarthest = i + nums[i]
        }
        if i == curEnd {
            curEnd = curFarthest
            if curEnd >= len(nums) - 1 {
                return true
            }
        }
    }
    return false
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func canJump(nums []int) bool {
    n := len(nums)
    dp := make([]bool, n)
    dp[n - 1] = true
        
    for i := n - 2; i >= 0; i-- {
        maxJump := min(i + nums[i], n - 1)
        for j := i + 1; j <= maxJump; j++ {
            dp[i] = dp[i] || dp[j]
        }
    }
                
    return dp[0]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 45. Jump Game II

leetcode

Dynamic Programming
This can be converted to a dp problem.
First, determine dp array, dp[i] means the minimum number of jumps from n - 1 to i.
Second, determine the iteration formula. For each index i, iterate j over i + 1 to maxJump, in which maxJump equals i + nums[i]. dp[i] = min(dp[i], dp[j] + 1).
Third, Initialize dp[n-1] = 0, because we only need to jump 0 times to n-1.
Fourth, determine the traversal order. We need two variables, i iterates from n - 2 to 0, j iterates from i + 1 to the maxJump of 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
func jump(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := 0; i < n - 1; i++ {
        dp[i] = math.MaxInt32
    }
    dp[n - 1] = 0
        
    for i := n - 2; i >= 0; i-- {
        maxJump := min(i + nums[i], n - 1)
        for j := i + 1; j <= maxJump; j++ {
            dp[i] = min(dp[i], dp[j] + 1)
        }
    }
                
    return dp[0]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

Greedy
Let’s say the range of current jump is [curBegin, curEnd], curFarthest is the farthest point that all points is [curBegin, curEnd] can reach. Once the current point reaches curEnd, then trigger another jump and set the new curEnd with curFarthest.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func jump(nums []int) int {
    curEnd, curFarthest := 0, 0
    jumps := 0
    for i := 0; i < len(nums) - 1; i++ {
        if i + nums[i] > curFarthest {
            curFarthest = i + nums[i]
        }
        if i == curEnd {
            jumps++
            curEnd = curFarthest
            if curEnd > len(nums) {
                break
            }
        }
    }
    return jumps
}

# 1306. Jump Game III

leetcode

At first glance, we could use BFS search. Because you can only jump to either i + arr[i] or i - arr[i], the algorithm complexity is O(2N). Because the arr is non-negative, we can use its negativity marked as traversed.

1
2
3
4
5
6
7
func canReach(arr []int, start int) bool {
    if start >= 0 && start < len(arr) && arr[start] >= 0 {
        arr[start] = -arr[start]
        return arr[start] == 0 || canReach(arr, start + arr[start]) || canReach(arr, start - arr[start])
    }
    return false
}

# 1871. Jump Game VII

leetcode

It’s a bottom-up DP implementation. The boolean value represents whether this position is reachable from start. So the first step is to generate the table. Here the table was pre-labeled True or False, thus '1’s are already labeled False.
To determine the state of dp[i], one need to check the states in window dp[i-maxJ : i-minJ], because any one of them can reach i if it’s labeled True.
Then you need to check if there is a True in this window. Notice that this is a sliding window problem, so you don’t need to calculate it everytime. You only need to remove the effect from dp[i-maxJ-1] and add the dp[i-minJ]. This is done by these two lines of code pre += dp[i - minJ] and pre -= dp[i - maxJ - 1]
The if statements if i >= minJ: and if i > maxJ: are dealing with the initial boundary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func canReach(s string, minJump int, maxJump int) bool {
    n := len(s)
    pre := 0
    dp := make([]bool, n)
    dp[0] = true
    for i := 1; i < n; i++ {
        if i >= minJump && dp[i - minJump] {
            pre += 1
        }
        if i > maxJump && dp[i - maxJump - 1] {
            pre -= 1
        }
        dp[i] = pre > 0 && s[i] == '0'
    }
    return dp[n - 1]
}

# 1345. Jump Game IV

leetcode

We can try brute force bfs search first. But time limit exceeds.

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
var indices map[int][]int
var visited []bool

func minJumps(arr []int) int {
    n := len(arr)
    indices = make(map[int][]int)
    visited = make([]bool, n)
    for i, v := range arr {
        if _, exists := indices[v]; exists {
            indices[v] = append(indices[v], i) 
        } else {
            indices[v] = []int{i}
        }
    }
    return bfs(arr, 0)
}

func bfs(arr []int, index int) int {
    if index < 0 || index >= len(arr) {
        return math.MaxInt32
    }
    if visited[index] {
        return math.MaxInt32
    }
    if index == len(arr) - 1 {
        return 0
    }
    visited[index] = true
    step := math.MaxInt32
    step = min(step, bfs(arr, index+1)+1)
    step = min(step, bfs(arr, index-1)+1)
    indiceList, exists := indices[arr[index]]
    if exists {
        for _, i := range indiceList {
            step = min(step, bfs(arr, i)+1)
        }
    }
    visited[index] = false
    return step
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

Optimization with iteration. The first one reaches the end is the minimum number of steps.
The first visit is the minimum number of steps. Clear the indices map to avoid revisiting.

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
func minJumps(arr []int) int {
    n := len(arr)
    indices := make(map[int][]int)
    visited := make([]bool, n)
    for i, v := range arr {
        if _, exists := indices[v]; exists {
            indices[v] = append(indices[v], i) 
        } else {
            indices[v] = []int{i}
        }
    }
    queue := make([][]int, 0, len(arr))
    queue = append(queue, []int{0, 0})
    
    for len(queue) > 0 {
        q := queue[0]
        step, index := q[0], q[1]
        queue = queue[1:]
        if index == n - 1 {
            return step
        }
        
        left := index - 1
        if left > 0 && !visited[left] {
            visited[left] = true
            queue = append(queue, []int{step + 1, left})
        }
        right := index + 1
        if right < n && !visited[right] {
            visited[right] = true
            queue = append(queue, []int{step + 1, right})
        }
        
        vals, exists := indices[arr[index]]
        if exists {
            for _, neib := range vals {
                if !visited[neib] {
                    visited[neib] = true
                    queue = append(queue, []int{step + 1, neib})
                }
            }
            indices[arr[index]] = []int{}
        }
    }
    return 0
}

# 62. Unique Paths

leetcode

It’s a typical combinatorial problem, which should be:

(m+nm)m+n \choose m (mm+n​)

But we can also use DP to solve this problem.

First determine the dp array, dp[i][j] means the number of possible unique paths to the ixj grid.
Second, determine the iteration formula. dp[i][j] is dependent on dp[i-1][j] and dp[i][j-1]. dp[i][j] = dp[i-1][j] + dp[i][j-1]
Third, initialize the array. dp[0][0] = 1. And grids with 1 width or 1 height only have 1 possible unique paths.
Fourth, determine the traversal order. It must be from left to right, and bottom to top.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := 0; i < m; i ++ {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for i := 0; i < n; i++ {
        dp[0][i] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

# 63. Unique Paths II

leetcode

It’s similar to 62, but be cautious to the initialization of the array. And if dp[i][j] is occupied by an obstacle, there is no path to it.

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
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m := len(obstacleGrid)
    n := len(obstacleGrid[0])
    
    dp := make([][]int, m)
    for i := 0; i < m; i ++ {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
        dp[i][0] = 1
    }
    for j := 0; j < n && obstacleGrid[0][j] == 0; j++ {
        dp[0][j] = 1
    }

    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if obstacleGrid[i][j] == 1 {
                continue
            }
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

# 64. Minimum Path Sum

leetcode

A dp problem.

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
func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    dp := make([][]int, m)
    for i := range grid {
        dp[i] = make([]int, n)
    }
    dp[0][0] = grid[0][0]
    for i := 1; i < m; i++ {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }
    for j := 1; j < n; j++ {
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
        }
    }
    return dp[m-1][n-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 70. Climbing Stairs

leetcode

It’s basically fibonacci problem.

1
2
3
4
5
6
7
8
9
10
11
12
func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

# 746. Min Cost Climbing Stairs

leetcode

It could be solved by dp.
First dp[i] means the minimum cost to reach the ith floor.
Second dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
Third initialize dp[0] = cost[0], dp[1] = cost[1]
Fourth traverse from left to right.
Finally return the minimum of the last two dp elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    dp[0], dp[1] = cost[0], cost[1]
    for i := 2; i < n; i++ {
        dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
    }
    return min(dp[n - 1], dp[n - 2])
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 72. Edit Distance

leetcode

It’s DP problem.
First dp[i][j] means the minimum operations between the first i - 1 characters in word1 and the first j - 1 characters in word2.
Second, if word1[i - 1] == word2[i - 2], there is no need to edit any characters. Otherwise, there’s different operations:

  1. word1 deletes an character, so the left i - 2 characters of word1 equals j - 1 characters of word2, dp[i][j] = dp[i - 1][j]
  2. word2 deletes an character, so the left i - 1 characters of word1 equals j - 2 characters of word2, dp[i][j] = dp[i][j - 1]
  3. the addition of character is the reversion of deletion.
  4. substitution, replace word1[i - 1] to match word2[j - 1], dp[i][j] = dp[i - 1][j - 1] + 1
    Third, initialize dp[0][0] = 0. For word1’s first i - 1 characters, there must be i operations to the empty word2.
    Fourth, left to right. Bottom to up.
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
func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i < m+1; i++ {
        dp[i][0] = i
    }
    for j := 0; j < n+1; j++ {
        dp[0][j] = j
    }
    for i := 1; i < m+1; i++ {
        for j := 1; j < n+1; j++ {
            if word1[i - 1] == word2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
            }
        }
    }
    return dp[m][n]
}

func min(args ...int) int {
  min := args[0]
  for _, item := range args {
    if item < min {
      min = item
    }
  }
  return min
}

# 85. Maximal Rectangle

leetcode

DP

Try to find the highest height and the longest right - left distance for each row.

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
51
52
53
54
55
56
57
58
func maximalRectangle(matrix [][]byte) int {
    rows, cols := len(matrix), len(matrix[0])
    left := make([]int, cols)
    right := make([]int, cols)
    height := make([]int, cols)
    for i := range right {
        right[i] = cols
    }
    
    maxA := 0
    for i := 0; i < rows; i++ {
        cur_left, cur_right := 0, cols
        for j := 0; j < cols; j++ {
            if matrix[i][j] == '1' {
                height[j] = height[j] + 1
            } else {
                height[j] = 0
            }
        }
        
        for j := 0; j < cols; j++ {
            if matrix[i][j] == '1' {
                left[j] = max(left[j], cur_left)
            } else {
                left[j] = 0
                cur_left = j + 1
            }
        }
        
        for j := cols - 1; j >=0 ;j-- {
            if matrix[i][j] == '1' {
                right[j] = min(right[j], cur_right)
            } else {
                right[j] = cols
                cur_right = j
            }
        }
        
        for j := 0; j < cols;j++ {
            maxA = max(maxA, (right[j] - left[j]) * height[j])
        }
    }
    return maxA
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 84. Largest Rectangle in Histogram

leetcode

Stack

The basic idea is traversing from left to right. There are 4 possibilities:

  1. There’s a rectangle forming just using the height of the current bar which has an area larger than the maxArea previously recorded.
  2. There’s a rectangle forming using the width or entire spread of the area starting from a bar seen long back which has an area larger than the current maxArea
  3. There’s a rectangle forming using width and height of recent tall bars which has an area larger than the current maxArea.
  4. There’s no rectangle with larger area at this step.
    So we have to find the possible bars which may form a larger rectangle and eliminate the impossible bars when we encounter a bar less than the bar we’ve before. So the stack is come into my mind.
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
func largestRectangleArea(heights []int) int {
    n := len(heights)
    stack := []int{}
    stack = append(stack, -1)
    heights = append(heights, 0)
    ans := 0
    for i, height := range heights {
        for {
            idx := stack[len(stack) - 1]
            if idx == -1 {
                idx = n
            }
            if heights[idx] <= height {
                break
            }
            h := heights[idx]
            stack = stack[:len(stack)-1]
            w := i - stack[len(stack)-1] - 1
            area := h * w
            if area > ans {
                ans = area
            }
        }
        stack = append(stack, i)
    }
    return ans
}

Two pointer

To find the last index from both the left and right where heights[l] >= heights[i] and heights[r] >= heights[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
28
func largestRectangleArea(heights []int) int {
    n := len(heights)
    right, left := make([]int, n), make([]int, n)
    right[n-1] = n
    left[0] = -1
    for i := 1; i < n; i++ {
        p := i - 1
        for p >= 0 && heights[p] >= heights[i] {
            p = left[p]
        }
        left[i] = p
    }
    for i := n - 2; i >= 0; i-- {
        p := i + 1
        for p < n && heights[p] >= heights[i] {
            p = right[p]
        }
        right[i] = p
    }
    maxA := 0
    for i := 0; i < n; i++ {
        area := (right[i] - left[i] - 1) * heights[i]
        if area > maxA {
            maxA = area
        }
    }
    return maxA
}

# 87. Scramble String

leetcode

Recursive

Straight forward way to check all possible substring by dividing the string into two parts and check whether both two parts are scrambled.
But unfortunately, simple recursive solution will get a time limit exceed error. We have to optimize using premature exit and memorization.

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
var store map[string]bool

func isScramble(s1 string, s2 string) bool {
    if store == nil {
        store = make(map[string]bool)
    }
    
    if len(s1) != len(s2) {
        return false
    }
    if s1 == s2 {
        return true
    }
    // shortcut to check the frequency of the letters
    m := make(map[byte]int)
    for i := range s1 {
        m[s1[i]]++
        m[s2[i]]--
    }
    for _, count := range m {
        if count > 0 {
            return false
        }
    }
    
    if val, ok := store[s1+s2]; ok {
        return val
    }
    
    n := len(s1)
    for i := 1; i <= n - 1; i++ {
        if isScramble(s1[:i], s2[:i]) && isScramble(s1[i:], s2[i:]) {
            store[s1 + s2] = true
            store[s2 + s1] = true
            return true
        }
        if isScramble(s1[:i], s2[n-i:]) && isScramble(s1[i:], s2[:n-i]) {
            store[s1 + s2] = true
            store[s2 + s1] = true
            return true
        }
    }
    store[s1 + s2] = false
    store[s2 + s1] = false
    return false
}

DP

DP is generalized from the memorized recursive solution. The dp[i][j][k] means whether the k length substring from i, j respectively are scramble strings.

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
func isScramble(s1 string, s2 string) bool {
    if s1 == s2 {
        return true
    }
    if len(s1) != len(s2) {
        return false
    }
    n := len(s1)
    dp := make([][][]bool, n)
    for i := range dp {
        dp[i] = make([][]bool, n)
        for j := range dp[i] {
            dp[i][j] = make([]bool, n+1)
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            dp[i][j][1] = s1[i] == s2[j]
        }
    }
    
    for l := 2; l <= n; l++ {
        for i := 0; i <= n - l; i++ {
            for j := 0; j <= n - l; j++ {
                for k := 1; k < l; k++{
                    a := dp[i][j][k] && dp[i + k][j + k][l - k]
                    b := dp[i][j + l - k][k] && dp[i + k][j][l - k]
                    if a || b {
                        dp[i][j][l] = true
                    }
                }
            }
        }
    }
    
    return dp[0][0][n]
}

# 312. Burst Balloons

leetcode

We could describe the whole process in reverse. Suppose we have a open interval (i, j), and the kth ballon is the last ballon which will be bursted. Then the coins we can get is:
nums[i] * nums[j] * nums[k] + coins(i, k) + coins(k, j)
Determine the traversal order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxCoins(nums []int) int {
    nums = append([]int{1}, nums...)
    nums = append(nums, 1)
    n := len(nums)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    
    for i := n - 1; i >= 0; i-- {
        for j := i + 1; j < n; j++ {
            for k := i + 1; k < j; k++ {
                coin := nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]
                if coin > dp[i][j] {
                    dp[i][j] = coin
                }
            }
        }
    }
    return dp[0][n-1]
}

# 1246. Palindrome Removal

csdn

It’s problem to find the minimal number of operations in an interval.
dp[i][j] means the minimal number of delete operations in the interval [i, j], left closed, right closed.
If i == j, the dp[i][i] = 1, there only needs 1 operation, because there is only one character.
If j - i == 1, if the arr[i] == arr[j], dp[i][j] = 1, otherwise dp[i][j] = 2
If j - i > 1, we have to check if arr[i] == arr[j]. If so, dp[i][j] = dp[i + 1][j - 1]. Otherwise, we could use divide and conquer. Suppose k divides interval into [i,k][k,j], we need to find the least dp[i][k] + dp[k+1][j].
Determine the traversal order. It can be the outer iterate from 0 to n, the inner loop iterate from i to 0. Or the outer loop iterate from n to 0, the inner loop iterate from i to n.

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
func minimumMoves(arr []int) int {
  n := len(arr)
  dp := make([][]int, n)
  for i := range dp {
    dp[i] = make([]int, n)
  }
  for i := n - 1; i >= 0; i-- {
    for j := i; j < n; j++ {
      if arr[i] == arr[j] {
        if j - i <= 1 {
          dp[i][j] = j - 1 + 1
          continue
        } else {
          dp[i][j] = dp[i + 1][j - 1]
        }
      }
      for k := i; k < j; k++ {
        cost := dp[i][k] + dp[k+1][j]
        if cost < dp[i][j] {
          dp[i][j] = cost
        }
      }
    }
  }
  return dp[0][n-1]
}

# 322. Coin Change

leetcode

Review the complete knapsack problem.

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
func coinChange(coins []int, amount int) int {
    n := len(coins)
    dp := make([]int, amount+1)
    for i := 1; i < amount+1; i++ {
        dp[i] = math.MaxInt32
    }
    for i := 0; i < n; i++ {
        for j := coins[i]; j <= amount; j++ {
            if dp[j - coins[i]] == math.MaxInt32 {
                continue
            }

            dp[j] = min(dp[j - coins[i]] + 1, dp[j])
        }
    }
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 518. Coin Change 2

This is a complete knapsack problem.
Here, we are look for the combination number.

1
2
3
4
5
6
7
8
9
10
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for i := 0; i < len(coins); i++ {
        for j := coins[i]; j <= amount; j++ {
            dp[j] += dp[j - coins[i]]
        }
    }
    return dp[amount]
}

But what if we are look for the permutation number.
We use the same coin more than once.

1
2
3
4
5
6
7
8
9
10
11
12
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for j := 0; j <= amount; j++ {
        for i := 0; i < len(coins); i++ {
            if j > coins[i] {
              dp[j] += dp[j - coins[i]]
            }
        }
    }
    return dp[amount]
}

# 416. Partition Equal Subset Sum

leetcode

The problem can be converted to whether we can find a subarray with the sum of total_sum / 2, which is a 0-1 knapsack problem. If we can fill the sum/2 weighted knapsack with sum/2 valued items.

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
func canPartition(nums []int) bool {
    if len(nums) == 1 {
        return false
    }
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum % 2 != 0 {
        return false
    }
    size := sum / 2
    dp := make([]int, size+1)
    for i := 0; i < len(nums); i++ {
        for j := size; j >= nums[i]; j-- {
            dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
        }
    }
    return dp[size] == size 
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 96. Unique Binary Search Trees

leetcode

for n = 1 there is 1 tree
dp[1] = dp[0] * dp[0]
for n = 2 there is 2 tree
dp[2] = dp[0] * dp[1] + dp[1] * dp[0]
for n = 3 there is 5 tree
dp[3] = dp[0] * dp[2] + dp[1] * dp[1] + dp[2] * dp[0]

1
2
3
4
5
6
7
8
9
10
func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        for j := 1; j <= i; j++ {
            dp[i] += dp[j - 1] * dp[i - j]
        }
    }
    return dp[n]
}

# 91. Decode Ways

leetcode

Recursion

Time Complexity O(2^N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func numDecodings(s string) int {
    if len(s) == 0 {
        return 0
    }
    return recurse(0, s)
}

func recurse(p int, s string) int {
    if p == len(s) {
        return 1
    }
    if s[p] == '0' { // sub string starting with 0 is not a valid encoding
        return 0
    }
    res := recurse(p+1, s)
    if p < len(s) - 1 && (s[p] == '1' || s[p] == '2' && s[p+1] <= '6') {
        res += recurse(p+2, s)
    }
    return res
}

Memorization

Time Complexity O(N)
Space Complexity O(N)

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
func numDecodings(s string) int {
    if len(s) == 0 {
        return 0
    }
    mem := make([]int, len(s)+1)
    for i := range mem {
        mem[i] = -1
    }
    return recurse(0, s, mem)
}

func recurse(p int, s string, mem []int) int {
    if mem[p] > -1 {
        return mem[p]
    }
    if p == len(s) {
        mem[p] = 1
        return 1
    }
    if s[p] == '0' { // sub string starting with 0 is not a valid encoding
        mem[p] = 0
        return 0
    }
    res := recurse(p+1, s, mem)
    if p < len(s) - 1 && (s[p] == '1' || s[p] == '2' && s[p+1] <= '6') {
        res += recurse(p+2, s, mem)
    }
    mem[p] = res
    return res
}

DP

Time Complexity O(N)
Space Complexity o(N)

Copy from memorization

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
func numDecodings(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = 0
    }
    dp[n] = 1
    
    for i := n - 1; i >= 0; i-- {
        if s[i] == '0' {
            dp[i] = 0
            continue
        }
        // dp[i+1]
        dp[i] += dp[i+1]
        // dp[i+2]
        if i < len(s) - 1 && (s[i] == '1' || s[i] == '2' && s[i+1] <= '6') {
            dp[i] += dp[i+2]
        }
    }
    return dp[0]
}

bottom up

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func numDecodings(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    dp := make([]int, n+1)
    dp[0] = 1
    if s[0] == '0' {
        return 0
    }
    dp[1] = 1
    for i := 2; i <= n; i++ {
        first, second := s[i-2], s[i-1]
        if second != '0' {
            dp[i] += dp[i-1]
        }
        if first == '1' || first == '2' && second <= '6' {
            dp[i] += dp[i-2]
        }
    }
    return dp[n]
}

DP Constant Space

Time Complexity O(N)
Space Complexity O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func numDecodings(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    dp2, dp1 := 0, 1
    
    for i := n - 1; i >= 0; i-- {
        dp := 0
        if s[i] != '0' {
            dp = dp1
        }
        if i < len(s) - 1 && (s[i] == '1' || s[i] == '2' && s[i+1] <= '6') {
            dp += dp2
        }
        dp2 = dp1
        dp1 = dp
    }
    return dp1
}

# 639. Decode Ways II

leetcode

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
func numDecodings(s string) int {
    n := len(s)
    if n == 0 {
        return 0
    }
    if s[0] == '0' {
        return 0
    }
    dp := make([]int, n+1)
    dp[0] = 1
    if s[0] == '*' {
        dp[1] = 9
    } else {
        dp[1] = 1
    }

    for i := 2; i <= n; i++ {
        first, second := s[i-2], s[i-1]
        if second == '*' {
            dp[i] += 9*dp[i-1]
        } else if (second > '0') {
            dp[i] += dp[i-1]
        }
        
        if first == '*' {
            if second  == '*' {
                dp[i] += 15*dp[i-2]
            } else if second <= '6' {
                dp[i] += 2*dp[i-2]
            } else {
                dp[i] += dp[i-2]
            }
        } else if first == '1' || first == '2' {
            if second == '*' {
                if first == '1' {
                    dp[i] += 9*dp[i-2]
                } else {
                    dp[i] += 6*dp[i-2]
                }
            } else if first == '1' || first == '2' && second <= '6' {
                dp[i] += dp[i-2]
            }
        }
        dp[i] %= 1000000007
    }
    return dp[n]
}

# 97. Interleaving String

leetcode

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isInterleave(s1 string, s2 string, s3 string) bool {
    if len(s1) + len(s2) != len(s3) {
        return false
    }
    if len(s1) == 0 {
        return s2 == s3
    }
    if len(s2) == 0 {
        return s1 == s3
    }
    res := false
    if s1[0] == s3[0] {
        res = res || isInterleave(s1[1:], s2, s3[1:])
    }
    if s2[0] == s3[0] {
        res = res || isInterleave(s1, s2[1:], s3[1:])
    }
    return res
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isInterleave(s1 string, s2 string, s3 string) bool {
    if len(s1) + len(s2) != len(s3) {
        return false
    }
    dp := make([][]bool, len(s1)+1)
    for i := range dp {
        dp[i] = make([]bool, len(s2)+1)
    }
    for i := 0; i <= len(s1); i++ {
        for j := 0; j <= len(s2); j++ {
            if i == 0 && j == 0 {
                dp[i][j] = true
            } else if i == 0 {
                dp[i][j] = dp[i][j-1] && s2[j-1] == s3[i+j-1]
            } else if j == 0 {
                dp[i][j] = dp[i-1][j] && s1[i-1] == s3[i+j-1]
            } else {
                dp[i][j] = (dp[i-1][j] && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1])
            }
        }
    }
    return dp[len(s1)][len(s2)]
}

# 115. Distinct Subsequences

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func numDistinct(s string, t string) int {
    if len(s) < len(t) {
        return 0
    }
    dp := make([][]int, len(s)+1)
    for i := range dp {
        dp[i] = make([]int, len(t)+1)
    }
    for i := 0; i <= len(s); i++ {
        dp[i][0] = 1
    }
    // the first column is 0 by default in every other rows but the first, which we need.
    for i := 1; i <= len(s); i++ {
        for j := 1; j <= len(t); j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[len(s)][len(t)]
}

# 118. Pascal’s Triangle

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func generate(numRows int) [][]int {
    result := make([][]int, 0, numRows)
    result = append(result, []int{1})
    if numRows == 1 {
        return result
    }
    result = append(result, []int{1, 1})
    if numRows == 2 {
        return result
    }
    for i := 3; i <= numRows; i++ {
        res := make([]int, i)
        for j := 0; j < i; j++ {
            if j == 0 || j == i - 1 {
                res[j] = 1
                continue
            }
            res[j] = result[i-2][j-1] + result[i-2][j]
        }
        result = append(result, res)
    }
    return result
}

# 119. Pascal’s Triangle II

leetcode

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func getRow(rowIndex int) []int {
    result := make([][]int, 0, rowIndex)
    result = append(result, []int{1})
    if rowIndex == 0 {
        return result[0]
    }
    result = append(result, []int{1, 1})
    if rowIndex == 1 {
        return result[1]
    }
    for i := 3; i <= rowIndex+1; i++ {
        res := make([]int, i)
        for j := 0; j < i; j++ {
            if j == 0 || j == i - 1 {
                res[j] = 1
                continue
            }
            res[j] = result[i-2][j-1] + result[i-2][j]
        }
        result = append(result, res)
    }
    return result[rowIndex]
}

Extra ith Space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func getRow(rowIndex int) []int {
    result := make([]int, rowIndex+1)
    result[0] = 1
    if rowIndex == 0 {
        return result[:1]
    }
    result[1] = 1
    if rowIndex == 1 {
        return result[:2]
    }
    for i := 3; i <= rowIndex+1; i++ {
        result[i-1] = 1
        first, second := result[0], result[1]
        for j := 1; j < i - 1; j++ {
            result[j] = first + second
            first, second = second, result[j+1]
        }
    }
    return result
}

# 120. Triangle

leetcode\

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func minimumTotal(triangle [][]int) int {
    m := len(triangle)
    n := len(triangle[m-1])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for j := 0; j < n; j++ {
        dp[m-1][j] = triangle[m-1][j]
    }
    for i := m - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
        }
    }
    return dp[0][0]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

O(N) SPACE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func minimumTotal(triangle [][]int) int {
    m := len(triangle)
    n := len(triangle[m-1])
    dp := make([]int, n)
    for j := 0; j < n; j++ {
        dp[j] = triangle[m-1][j]
    }
    for i := m - 2; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]
        }
    }
    return dp[0]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 123. Best Time to Buy and Sell Stock III

leetcode

DP

It’s not difficult to get the DP recursive formula:

dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j-1]), j=[0…i-1]
For k transactions, on i-th day, if we don’t trade then the profit is same as previous day dp[k, i-1];
and if we bought the share on j-th day where j=[0…i-1], then sell the share on i-th day then the profit is prices[i] - prices[j] + dp[k-1, j-1] .
Actually j can be i as well. When j is i, the one more extra item prices[i] - prices[j] + dp[k-1, j] = dp[k-1, i] looks like we just lose one chance of transaction.

I see someone else use the formula dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j]), where the last one is dp[k-1, j] instead of dp[k-1, j-1]. It’s not the direct sense, as if the share was bought on j-th day, then the total profit of previous transactions should be done on (j-1)th day. However, the result based on that formula is also correct, because if the share was sold on j-th day and then bought again, it is the same if we didn’t trade on that day.

Time Limit Exceeded

Time complexity is O(kn^2), space complexity is O(kn).

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
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    t := 2
    n := len(prices)
    dp := make([][]int, t+1)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for k := 1; k <= t; k++ {
        for i := 1; i < n; i++ {
            m := prices[0]
            for j := 1; j < i; j++ {
                m = min(m, prices[j] - dp[k - 1][j - 1])
            }
            dp[k][i] = max(dp[k][i - 1], prices[i] - m)
        }
    }
    return dp[t][n-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Remove duplicated calculation

Time complexity is O(kn), space complexity is O(kn).

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
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    t := 2
    n := len(prices)
    dp := make([][]int, t+1)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for k := 1; k <= t; k++ {
        m := prices[0]
        for i := 1; i < n; i++ {
            m = min(m, prices[i] - dp[k - 1][i - 1])
            dp[k][i] = max(dp[k][i - 1], prices[i] - m)
        }
    }
    return dp[t][n-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Swap the loops

Time complexity is O(kn), space complexity is O(kn + k).

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
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    t := 2
    n := len(prices)
    dp := make([][]int, t+1)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    m := make([]int, t+1)
    for i := range m {
        m[i] = prices[0]
    }
    for i := 1; i < n; i++ {
        for k := 1; k <= t; k++ {
            m[k] = min(m[k], prices[i] - dp[k - 1][i - 1])
            dp[k][i] = max(dp[k][i - 1], prices[i] - m[k])
        }
    }
    return dp[t][n-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Compact Dimension

Time Complexity O(kN)
Space Complexity O(2k)

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
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    t := 2
    n := len(prices)
    dp := make([]int, t+1)
    m := make([]int, t+1)
    for i := range m {
        m[i] = prices[0]
    }
    for i := 1; i < n; i++ {
        for k := 1; k <= t; k++ {
            m[k] = min(m[k], prices[i] - dp[k - 1])
            dp[k] = max(dp[k], prices[i] - m[k])
        }
    }
    return dp[t]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Name Expansion

# 188. Best Time to Buy and Sell Stock IV

leetcode

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
func maxProfit(k int, prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    t := k
    n := len(prices)
    dp := make([]int, t+1)
    m := make([]int, t+1)
    for i := range m {
        m[i] = prices[0]
    }
    for i := 1; i < n; i++ {
        for k := 1; k <= t; k++ {
            m[k] = min(m[k], prices[i] - dp[k - 1])
            dp[k] = max(dp[k], prices[i] - m[k])
        }
    }
    return dp[t]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 309. Best Time to Buy and Sell Stock with Cooldown

leetcode

s0 NONE <- s0, s2
s1 BOUGHT <- s1, s0 - prices[i]
s2 COOL DOWN <- s1 + prices[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
func maxProfit(prices []int) int {
    n := len(prices)
    s := make([][]int, 3)
    for i := range s {
        s[i] = make([]int, n)
    }
    s[0][0] = 0
    s[1][0] = -prices[0]
    s[2][0] = math.MinInt32
    
    for i := 1; i < n; i++ {
        s[0][i] = max(s[0][i-1], s[2][i-1])
        s[1][i] = max(s[1][i-1], s[0][i-1] - prices[i])
        s[2][i] = s[1][i-1] + prices[i]
    }
    return max(s[0][n-1], s[2][n-1])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 131. Palindrome Partitioning

leetcode

Backtracking DFS

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
func partition(s string) [][]string {
    list := []string{}
    return dfs(s, 0, list)
}

func dfs(s string, pos int, list []string) [][]string {
    result := [][]string{}
    if pos == len(s) {
        tmp := make([]string, len(list))
        copy(tmp, list)
        result = append(result, tmp)
        return result
    }
    for i := pos; i < len(s); i++ {
        if isPal(s[pos:i+1]) {
            list = append(list, s[pos:i+1])
            result = append(result, dfs(s, i+1, list)...)
            list = list[:len(list)-1]
        }
    }
    return result
}

func isPal(s string) bool {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            return false
        }
    }
    return true
}

DP DFS

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
func partition(s string) [][]string {
    list := []string{}
    m := len(s)
    dp := make([][]bool, m)
    for i := range dp {
        dp[i] = make([]bool, m)
    }
    for i := 0; i < m; i++ {
        for j := 0; j <= i; j++ {
            if s[i] == s[j] {
                if i - j <= 2 {
                    dp[j][i] = true
                } else if dp[j - 1][i + 1] {
                    dp[j][i] = true
                }
            }
        }
    }
    return dfs(s, 0, list, dp)
}

func dfs(s string, pos int, list []string, dp [][]bool) [][]string {
    result := [][]string{}
    if pos == len(s) {
        tmp := make([]string, len(list))
        copy(tmp, list)
        result = append(result, tmp)
        return result
    }
    for i := pos; i < len(s); i++ {
        if dp[pos][i] {
            list = append(list, s[pos:i+1])
            result = append(result, dfs(s, i+1, list, dp)...)
            list = list[:len(list)-1]
        }
    }
    return result
}

DP

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
func partition(s string) [][]string {
    result := [][][]string{}
    result = append(result, [][]string{[]string{}})
    
    m := len(s)
    dp := make([][]bool, m)
    for i := range dp {
        dp[i] = make([]bool, m)
    }
    for i := 0; i < m; i++ {
        result = append(result, [][]string{})
        for j := 0; j <= i; j++ {
            if s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1]) {
                dp[j][i] = true
                str := s[j:i+1]
                for _, r := range result[j] {
                    ri := make([]string, len(r))
                    copy(ri, r)
                    ri = append(ri, str)
                    result[i+1] = append(result[i+1], ri)
                }
            }
        }
    }
    return result[m]
}

# 132. Palindrome Partitioning II

leetcode

  1. cut[i] is the minimum of cut[j - 1] + 1 (j <= i) if [j, i] is palindrome
  2. If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and cut[j] == cut[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
28
29
30
func minCut(s string) int {
    m := len(s)
    dp := make([][]bool, m)
    for i := range dp {
        dp[i] = make([]bool, m)
    }
    cut := make([]int, m)
    
    for i := 0; i < m; i++ {
        cut[i] = i
        for j := 0; j <= i; j++ {
            if s[i] == s[j] && (i - j <= 1 || dp[j+1][i-1]) {
                dp[j][i] = true
                if j == 0 {
                    cut[i] = 0
                } else {
                    cut[i] = min(cut[i], cut[j - 1] + 1)
                }
            }
        }
    }
    return cut[m-1]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 1278. Palindrome Partitioning III

leetcode

Time Complexity O(N^2)

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
func palindromePartition(s string, k int) int {
    mem := make(map[string]int)
    return dfs(0, k, s, mem)
}

func cost(s string) int {
    c := 0
    for i, j := 0, len(s) - 1; i < j; i, j = i+1, j-1 {
        if s[i] != s[j] {
            c++
        }
    }
    return c
}

func dfs(i, k int, s string, mem map[string]int) int {
    if change, exists := mem[fmt.Sprintf("%d,%d", i, k)]; exists {
        return change
    }
    if len(s) - i == k {
        return 0
    }
    if k == 1 {
        return cost(s[i:])
    }
    res := math.MaxInt32
    for j := i + 1; j <= len(s) - k + 1; j++ {
        res = min(res, dfs(j, k - 1, s, mem) + cost(s[i:j]))
    }
    mem[fmt.Sprintf("%d,%d", i, k)] = res
    return res
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 1745. Palindrome Partitioning IV

leetcode

We can now check, if left, mid and right are all palindrom, and return true.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func checkPartitioning(s string) bool {
    m := len(s)
    dp := make([][]bool, m)
    for i := range dp {
        dp[i] = make([]bool, m)
    }

    for i := 0; i < m; i++ {
        for j := 0; j <= i; j++ {
            if s[i] == s[j] && (i - j <= 1 || dp[j+1][i-1]) {
                dp[j][i] = true
            }
        }
    }
    
    for i := 2; i < m; i++ {
        for j := 0; j <= i; j++ {
            if dp[0][j] && dp[j+1][i-1] && dp[i][m-1] {
                return true
            }
        }
    }
    return false
}

# 139. Word Break

leetcode

BackTracking With Mem

Time Complexity O(N^2), Worst O(2^N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func wordBreak(s string, wordDict []string) bool {
    d := make(map[string]bool)
    for _, word := range wordDict {
        d[word] = true
    }
    return dfs(s, d)
}

func dfs(s string, d map[string]bool) bool {
    if value, exists := d[s]; exists {
        return value
    }
    for i := 1; i < len(s); i++ {
        if dfs(s[:i], d) && dfs(s[i:], d) {
            d[s] = true
            return true
        }
    }
    d[s] = false
    return false
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func wordBreak(s string, wordDict []string) bool {
    d := make(map[string]bool)
    for _, word := range wordDict {
        d[word] = true
    }
    
    dp := make([]bool, len(s) + 1)
    dp[0] = true
    
    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] {
                if _, exists := d[s[j:i]]; exists {
                    dp[i] = true
                    break
                }
            }
        }
    }
    
    return dp[len(s)]
}

# 140. Word Break II

leetcode

Backtracking Filtered With Set

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
func wordBreak(s string, wordDict []string) []string {
    d := make(map[string]struct{})
    for _, word := range wordDict {
        d[word] = struct{}{}
    }
    
    m := make(map[string][]string)
    res := make(map[string]struct{})
    results := dfs(s, d, m)
    for _, result := range results {
        res[result] = struct{}{}
    }
    cleaned := []string{}
    for k := range res {
        cleaned = append(cleaned, k)
    }
    return cleaned
}

func dfs(s string, d map[string]struct{}, m map[string][]string) []string {
    if value, exists := m[s]; exists {
        return value
    }
    res := []string{}
    if len(s) == 0 {
        return res
    }
    if _, exists := d[s]; exists {
        res = append(res, s)
    }
    for i := 1; i < len(s); i++ {
        left := dfs(s[:i], d, m)
        right := dfs(s[i:], d, m) 
        if len(left) > 0 && len(right) > 0 {
            for _, l := range left {
                for _, r := range right {
                    res = append(res, l + " " + r)
                }
            }
        }
    }
    m[s] = res
    return res
}

Without Set

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
func wordBreak(s string, wordDict []string) []string {
    d := make(map[string]struct{})
    for _, word := range wordDict {
        d[word] = struct{}{}
    }
    
    m := make(map[string][]string)
    return dfs(s, d, m)
}

func dfs(s string, d map[string]struct{}, m map[string][]string) []string {
    if value, exists := m[s]; exists {
        return value
    }

    res := []string{}
    if len(s) == 0 {
        res = append(res, "")
        return res
    }
    
    for word := range d {
        if strings.HasPrefix(s, word) {
            sublist := dfs(s[len(word):], d, m)
            for _, sub := range sublist {
                if len(sub) != 0 {
                    sub = " " + sub
                }
                res = append(res, word + sub)
            }
        }
    }
    m[s] = res
    return res
}

# 472. Concatenated Words

leetcode

Combined with 140.

DP

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
func findAllConcatenatedWordsInADict(words []string) []string {
    result := []string{}
    preWords := make(map[string]struct{})
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })
    
    for i := 0; i < len(words); i++ {
        if canForm(words[i], preWords) {
            result = append(result, words[i])
        }
        preWords[words[i]] = struct{}{}
    }
    
    return result
}

func canForm(word string, dict map[string]struct{}) bool {
    if len(dict) == 0 {
        return false
    }
    
    dp := make([]bool, len(word) + 1)
    dp[0] = true
    for i := 1; i <= len(word); i++ {
        for j := 0; j < i; j++ {
            if !dp[j] {
                continue
            }
            if _, exists := dict[word[j:i]]; exists {
                dp[i] = true
                break
            }
        }
    }
    
    return dp[len(word)]
}

BackTracking

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
func findAllConcatenatedWordsInADict(words []string) []string {
    result := []string{}
    preWords := make(map[string]struct{})
    sort.Slice(words, func(i, j int) bool {
        return len(words[i]) < len(words[j])
    })
    
    for i := 0; i < len(words); i++ {
        if dfs(words[i], preWords) {
            result = append(result, words[i])
        }
        preWords[words[i]] = struct{}{}
    }
    
    return result
}

func dfs(word string, dict map[string]struct{}) bool {
    for i := 1; i < len(word); i++ {
        _, left := dict[word[:i]]
        _, right := dict[word[i:]]
        if left && right {
            return true
        }
        if left && dfs(word[i:], dict) {
            return true
        }
        if right && dfs(word[:i], dict) {
            return true
        }
    }
    return false
}

# 152. Maximum Product Subarray

leetcode

Greedy

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
func maxProduct(nums []int) int {
    r := nums[0]
    imax := r
    imin := r
    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            imax, imin = imin, imax
        }
        
        imax = max(nums[i], imax*nums[i])
        imin = min(nums[i], imin*nums[i])
        r = max(r, imax)
    }
    return r
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 174. Dungeon Game

leetcode

Backtracking

LTE

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
func calculateMinimumHP(dungeon [][]int) int {
    return getVal(dungeon, 0, 0)
}

func getVal(mat [][]int, i, j int) int {
    n, m := len(mat), len(mat[0])
    if i == n || j == m {
        return math.MaxInt32
    }
    if i == n - 1 && j == m - 1 {
        if mat[i][j] <= 0 {
            return -mat[i][j] + 1
        } else {
            return 1
        }
    }
    
    right := getVal(mat, i, j+1)
    down := getVal(mat, i+1, j)
    
    minHealth := min(right, down) - mat[i][j]
    if minHealth <= 0 {
        return 1
    }
    return minHealth
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

Backtracking With Memorization

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
func calculateMinimumHP(dungeon [][]int) int {
    n, m := len(dungeon), len(dungeon[0])
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, m)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt32
        }
    }
    return getVal(dungeon, dp, 0, 0)
}

func getVal(mat [][]int, dp[][]int, i, j int) int {
    n, m := len(mat), len(mat[0])
    if i == n || j == m {
        return math.MaxInt32
    }
    if i == n - 1 && j == m - 1 {
        if mat[i][j] <= 0 {
            return -mat[i][j] + 1
        } else {
            return 1
        }
    }
    
    if dp[i][j] < math.MaxInt32 {
        return dp[i][j]
    }
    
    right := getVal(mat, dp, i, j+1)
    down := getVal(mat, dp, i+1, j)
    
    minHealth := min(right, down) - mat[i][j]
    if minHealth <= 0 {
        dp[i][j] = 1
        return 1
    }
    dp[i][j] = minHealth
    return minHealth
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

DP

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
func calculateMinimumHP(dungeon [][]int) int {
    m, n := len(dungeon), len(dungeon[0])
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt32
        }
    }
    dp[m][n-1] = 1
    dp[m-1][n] = 1
    for i := m - 1; i >= 0; i-- {
        for j := n - 1; j >= 0; j-- {
            need := min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
            if need <= 0 {
                dp[i][j] = 1
            } else {
                dp[i][j] = need
            }
        }
    }
    return dp[0][0]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 198. House Robber

leetcode

Similar to stock trading with 2 states: rob or skip.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func rob(nums []int) int {
    n := len(nums)
    dp := make([][]int, 2)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[0][0] = 0
    dp[1][0] = nums[0]
    for i := 1; i < n; i++ {
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
        dp[1][i] = dp[0][i-1] + nums[i]
    }
    return max(dp[0][n-1], dp[1][n-1])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 213. House Robber II

leetcode

Either robbing from the first n-1 houses or the last n-1 houses.

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
func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    return max(robHelper(nums[1:]), robHelper(nums[:len(nums)-1]))
}

func robHelper(nums []int) int {
    n := len(nums)
    dp := make([][]int, 2)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    dp[0][0] = 0
    dp[1][0] = nums[0]
    for i := 1; i < n; i++ {
        dp[0][i] = max(dp[0][i-1], dp[1][i-1])
        dp[1][i] = dp[0][i-1] + nums[i]
    }
    return max(dp[0][n-1], dp[1][n-1])
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 221. Maximal Square

leetcode

This is quite similar to Maximal Rectangle but much easier, because square only depends on the three directions.

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
func maximalSquare(matrix [][]byte) int {
    m, n := len(matrix), len(matrix[0])
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    maxArea := 0
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if matrix[i-1][j-1] == '1' {
                dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
                maxArea = max(maxArea, dp[i][j])
            }
        }
    }
    return maxArea * maxArea
}

func min(args ...int) int {
  min := args[0]
  for _, item := range args {
    if item < min {
      min = item
    }
  }
  return min
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

# 233. Number of Digit One

leetcode

TAT

1
2
3
4
5
6
7
8
9
10
11
12
func countDigitOne(n int) int {
    ones := 0
    for m := 1; m <= n; m *= 10 {
        a, b := n/m, n%m
        ones += (a + 8) / 10 * m
        if a % 10 == 1 {
            ones += (b + 1)
        }
        // fmt. Printf("%v %v %v %v\n", m, a, b, ones)
    }
    return ones
}

(1) xyz * 1000 if d == 0
(2) xyz * 1000 + abc + 1 if d == 1
(3) xyz * 1000 + 1000 if d > 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int countDigitOne(int n) {

    if (n <= 0) return 0;
    int q = n, x = 1, ans = 0;
    do {
        int digit = q % 10;
        q /= 10;
        ans += q * x;
        if (digit == 1) ans += n % x + 1;
        if (digit >  1) ans += x;
        x *= 10;
    } while (q > 0);
    return ans;

}

# 263. Ugly Number

leetcode

Keep divided by 2,3,5 until not divisible, check whether the quotient is 1.
4 is 2x2.

1
2
3
4
5
6
7
8
func isUgly(n int) bool {
     for i := 2; i < 6 && n > 0; i++ {
        for n % i == 0 {
            n /= i
        }
    }
    return n == 1   
}

# 264. Ugly Number II

leetcode

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
func nthUglyNumber(n int) int {
    if n <= 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    t2, t3, t5 := 0, 0, 0
    k := make([]int, n)
    k[0] = 1
    for i := 1; i < n; i++ {
        k[i] = min(k[t2]*2, k[t3]*3, k[t5]*5)
        if k[i] == k[t2]*2 { t2++ }
        if k[i] == k[t3]*3 { t3++ }
        if k[i] == k[t5]*5 { t5++ }
    }
    return k[n-1]
}

func min(args ...int) int {
  min := args[0]
  for _, item := range args {
    if item < min {
      min = item
    }
  }
  return min
}

# 313. Super Ugly Number

leetcode

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
func nthSuperUglyNumber(n int, primes []int) int {
    if n <= 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    t := make([]int, len(primes))
    k := make([]int, n)
    k[0] = 1
    for i := 1; i < n; i++ {
        m := math.MaxInt32
        for j := 0; j < len(primes); j++ {
            m = min(m, k[t[j]] * primes[j])
        }
        k[i] = m
        for j := 0; j < len(primes); j++ {
            if k[i] == k[t[j]] * primes[j] {
                t[j]++
            }
        }
    }
    return k[n-1]    
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 1201. Ugly Number III

leetcode

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
func nthUglyNumber(n int, a, b, c int) int {
    left, right := 1, math.MaxInt32

    for left < right {
        mid := left + (right - left) / 2;
        if uglyNumbers(mid, a, b, c) >= n {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func gcd(a, b int) int {
    if a > 0 {
        return gcd(b % a, a)
    }
    return b
}

func lcm(a, b int) int {
    return a * b / gcd(a, b)
}

func uglyNumbers(m, a, b, c int) int {
    lcmab := lcm(a, b);
    lcmac := lcm(a, c);
    lcmbc := lcm(b, c);
    lcmabc := lcm(lcmab, c);
    return m / a + m / b + m /c - m / lcmab - m / lcmac - m / lcmbc + m / lcmabc
}

# 279. Perfect Squares

leetcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dp[0] = 0 
dp[1] = dp[0]+1 = 1
dp[2] = dp[1]+1 = 2
dp[3] = dp[2]+1 = 3
dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 } 
      = Min{ dp[3]+1, dp[0]+1 } 
      = 1        
dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 } 
      = Min{ dp[4]+1, dp[1]+1 } 
      = 2
            .
            .
            .
dp[13] = Min{ dp[13-1*1]+1, dp[13-2*2]+1, dp[13-3*3]+1 } 
       = Min{ dp[12]+1, dp[9]+1, dp[4]+1 } 
       = 2
            .
            .
            .
dp[n] = Min{ dp[n - i*i] + 1 },  n - i*i >=0 && i >= 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
  dp[0] = 0
    for i := 1; i <= n; i++ {
        for j := 1; j*j <= i; j++ {
      dp[i] = min(dp[i], dp[i - j*j] + 1)
    }
  }		
  return dp[n]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}

# 204. Count Primes

leetcode

Basic idea to find prime factor.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func countPrimes(n int) int {
    notPrime := make([]bool, n)
    count := 0
 
    for i := 2; i < n; i++ {
        if !notPrime[i] {
            count++
            for j := 2; i*j < n; j++ {
                notPrime[i*j] = true
            }
        }
    }

    return count   
}

# 300. Longest Increasing Subsequence

leetcode

Subsequence is not continuous.

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
func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := range dp {
        dp[i] = 1
    }
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    return max(dp...)
}

func max(args ...int) int {
    max := args[0]
  for _, item := range args {
    if item > max {
      max = item
    }
  }
  return max
}

Share 

 Previous post: Code - Array Next post: Code - Outline 

© 2022 Kleon

Theme Typography by Makito

Proudly published with Hexo