Leetcode Dynamic Programming Problem Collection (1)

Green hand in DP problem
The key of Dynamic Programming is to get local result, then get global result.

  • 70.Climbing Stairs
  • 121.Best Time to Buy and Sell Stock *
  • 53.Maximum Subarray
  • 198.House Robber
  • 746.Min Cost Climbing Stairs
  • 42.Trapping Rain Water

70. Climbing Stairs

Tried to use recursion but it was super slow. Use iteration is much faster.

calculate the previous step 1 and step 2, keep tracking it. Time = O(n)

1
2
3
4
5
6
7
8
def climbStairs(self, n: int) -> int:
    if n == 1 or n == 2:
    	return n
    p1, p2 = 1, 2
    for i in range(3, n + 1):
        cur = p1 + p2
        p1, p2 = p2, cur
    return cur

121. Best Time to Buy and Sell Stock

I like this one. logging the lowest buying price while updating max profit

1
2
3
4
5
6
7
8
9
def maxProfit(self, prices: List[int]) -> int:
    if len(prices) < 1:
        return 0
    lowest = prices[0]
    profit = 0
    for price in prices:
        lowest = min(lowest, price)
        profit = max(profit, price - lowest)
    return profit

53. Maximum Subarray

Greedy

find local max sum, update global max sum if greater.

1
2
3
4
5
6
7
8
def maxSubArray(self, nums: List[int]) -> int:
    max_sum = nums[0]
    cur_sum = nums[0]
    
    for num in nums[1:]:
        cur_sum = max(cur_sum + num, num)
        max_sum = max(cur_sum, max_sum)
    return max_sum

Dynamic Programming

1
2
3
4
5
6
def maxSubArray(self, nums: List[int]) -> int:
    dp = [0] * len(nums)
    for i, num in enumerate(nums)
        dp[i] = max(dp[i - 1] + num, num)

    return max(dp)

198. House Robber

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def rob(self, nums: List[int]) -> int:
    if len(nums) < 3:
        return max(nums, default=0)
    
    gain = [0] * len(nums)
    gain[0], gain[1] = nums[0], max(nums[0], nums[1])
    
    for i in range(2, len(nums)):
        # Two options:
        # 1) rob it, gain(i) = gain(i-2) + current money
        # 2) don't rob it, current max gain is gain(i - 1)
        gain[i] = max(gain[i - 2] + nums[i], gain[i - 1])
    
    return gain[-1]

746. Min Cost Climbing Stairs

Either pay the last step, or pay the second last step

1
2
3
4
5
def minCostClimbingStairs(self, cost: List[int]) -> int:
    s0, s1 = cost[0], cost[1]
    for i in range(2, len(cost)):
        s1, s0 = min(cost[i] + s0, cost[i] + s1), s1
    return min(s0, s1)

42. Trapping Rain Water

DP solution, log left max, then log right max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def trap(self, height: List[int]) -> int:
    if len(height) < 3:
        return 0
    
    left_max, right_max = 0, 0
    
    # left, right, rain
    dp = [[0, 0] for _ in range(len(height))]
    
    # find left max:
    for i, h in enumerate(height):
        dp[i][0] = left_max
        left_max = max(h, left_max)
    
    res = 0
    # find right max, calculate rain
    for i in range(len(height) - 1, -1, -1):
        dp[i][1] = right_max
        right_max = max(right_max, height[i])
        res += max(min(dp[i][0], dp[i][1]) - height[i], 0)
    return res

It also has a stack solution.