Summary of Dynamic Programming III. (House Robber and Stock)
LeetCode 198 House Robber
We can consider recursion as a top-down algorithm, and dynamic programming as a bottom-up algorithm.
Let’s define dp[i] as the max amount of money you can rob if there are i houses. The value of dp[i] depends on whether you rob the ith house or not. If you rob the ith house, then dp[i] = dp[i-2]+nums[i]. If you don’t rob the ith house, then dp[i] = dp[i-1]. Therefore, the recurrence relation is dp[i] = max(dp[i-2] + nums[i], dp[i-1]).
The base case is dp[0] = nums[0] if there is one house. dp[1] = max(nums[0],nums[1]) if there are two houses. The result is stored in dp[len(nums)-1].
The time complexity is O(n), space complexity is O(n).
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[-1]
class Solution(object):
def rob(self, nums):
cur, pre = 0, 0
for n in nums:
cur, pre = max(pre + n, cur), cur
return cur
LeetCode 213 House Robber II
Let’s define dp[i] as the max amount of money you can rob if there are i houses. Similar to LC 198, but we have to consider three scenarios:
a] Suppose you do not rob the first and the last houses.
b] Suppose you do not rob the first house (you can rob the last one).
c] Suppose you do not rob the last house (you can rob the first one).
class Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 1:
return nums[0]
# do not rob the first house
val1 = self.robRange(nums[1:])
# do not rob the last house
val2 = self.robRange(nums[:-1])
return max(val1, val2)
def robRange(self, numlist):
dp = [0] * len(numlist)
dp[0] = numlist[0]
for i in range(1, len(numlist)):
if i == 1: # len(numlist) can be 1
dp[1] = max(numlist[0],numlist[1])
else:
dp[i] = max(dp[i-2]+numlist[i], dp[i-1])
return dp[-1]
LeetCode 337 House Robber III
Rather than iterating through a list, we recurse on a tree structure now. Because it is a recursion process, the order is from the leaves to the root.
Let’s define an array of size 2 for each node in the tree {val1, val2}, as the max amount of money if you rob the current node (val1) and if you don’t rob the current node (val2).
If you rob the current node, you don’t rob the children houses. If you do not rob the current node, you can decide rob or not rob the children houses
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: TreeNode) -> int:
res = self.robTree(root)
return max(res[0], res[1])
def robTree(self, node):
if node is None:
return (0,0)
left = self.robTree(node.left)
right = self.robTree(node.right)
# rob the current, do not rob the children
val1 = node.val + left[1] + right[1]
# do not rob the current, choose to rob or not rob the children
val2 = max(left[0],left[1]) + max(right[0],right[1])
return (val1, val2) # rob, not rob
LeetCode 121 Best Time to Buy and Sell Stock
Define dp[i][0] as the max profit when you have a stock on the ith day, and dp[i][1] as the max profit when you don’t have a stock on the ith day.
dp[i][0] can come from 1) dp[i-1][0] if you have the stock on the i-1th day; 2) -price[i] if you buy a stock on the ith day.
We want the max profit, so the recurrent relation is dp[i][0] = max(dp[i-1][0], -price[i]).
dp[i][1] can come from 1) dp[i-1][1] if you don’t have any stock on the i-1th day; 2) price[i]+dp[i-1][0] if you sell the stock on the ith day.
We want the max profit, so the recurrent relation is dp[i][1] = max(dp[i-1][1], price[i]+dp[i-1][0]).
The base case is dp[0][0]=-price[0] because you buy a stock on the first day, and dp[0][1]=0 because you don’t have any stock on the first day.
The result is dp[-1][1] because you have to sell the stock by the final day.
The time complexity is O(n). The space complexity is O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0]*2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,length):
dp[i][0] = max(dp[i-1][0], -prices[i]) # have stock
dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0]) # don't have stock
return dp[-1][1]
Since dp[i] only depends on dp[i-1], we can optimize the space complexity by applying rolling array. So the space complexity becomes O(1).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0]*2 for _ in range(2)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1,length):
dp[i%2][0] = max(dp[(i-1)%2][0], -prices[i]) # have stock
dp[i%2][1] = max(dp[(i-1)%2][1], prices[i]+dp[(i-1)%2][0]) # don't have stock
return dp[(length-1)%2][1]
LeetCode 122 Best Time to Buy and Sell Stock II
Key: One stock can be bought and sold many times.
Define dp[i][0] as the max profit when you have a stock on the ith day, and dp[i][1] as the max profit when you don’t have a stock on the ith day.
dp[i][0] can come from 1) dp[i-1][0] if you have stock on the day before; 2) dp[i-1][1]-prices[i] if you have sold one and buy another one.
dp[i][1] can come from 1) dp[i-1][1] if you don’t have any stock on the day before; 2) dp[i-1][0]+prices[i] if you have had one and sold it on the ith day.
Time complexity O(n). Space complexity O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(length)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
return dp[-1][1]
Optimize space complexity to O(1) by apply rolling array.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
dp = [[0] * 2 for _ in range(2)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, length):
dp[i%2][0] = max(dp[(i-1)%2][0], dp[(i-1)%2][1]-prices[i])
dp[i%2][1] = max(dp[(i-1)%2][1], dp[(i-1)%2][0]+prices[i])
return dp[(length-1)%2][1]
LeetCode 123 Best Time to Buy and Sell Stock III
Key: You may complete at most two transactions.
There can be five statues. 1) no action; 2) buy in for the first time; 3) sell out for the first time; 4) buy in for the second time; 5) sell out for the second time.
Define dp[i][j] (where j in {0,1,2,3,4}) as the max money you have on the ith day with status j.
One way to get to dp[i][0]: dp[i-1][0] when you have no action on the day before. The recurrence relation is dp[i][0] = dp[i-1][0].
Two ways to get to dp[i][1]: 1) dp[i-1][1] if you already buy a stock for the first time; 2) dp[i-1][0]-prices[i]if you buy a stock for the first time on the ith day. The recurrence relation is dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]).
Two ways to get to dp[i][2]: 1) dp[i-1][2] if you already sell a stock for the first time; 2) dp[i-1][1]+prices[i] if you sell a stock for the first time on the ith day. The recurrence relation is dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i]).
Two ways to get to dp[i][3]: 1) dp[i-1][3] if you already buy a stock for the second time; 2) dp[i-1][2]-prices[i] if you buy a stock for the second time on the ith day. The recurrence relation is dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i]).
Two ways to get to dp[i][4]: 1) dp[i-1][4] if you already sell a stock for the second time; 2) dp[i-1][3]-prices[i] if you sell a stock for the second time on the ith day. The recurrence relation is dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i]).
The base case dp[0][0] = 0 because you have no action on the 0th day. dp[0][1]=-prices[0] because you buy a stock on the 0th day.dp[0][2]=0 because you buy one and sell it on the 0th day. dp[0][3]=-prices[0] because you buy, sell, and buy one stock on the 0th day. dp[0][4]=0 because you buy, sell, buy and sell a stock on the 0th day.
Time complexity is O(n). Space complexity O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [[0]*5 for _ in range(length)]
dp[0][1] = -prices[0]
dp[0][3] = -prices[0]
for i in range(1, length):
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
return dp[-1][4]
LeetCode 188 Best Time to Buy and Sell Stock IV
Key: You may complete at most k transactions.
Since you may complete at most k transactions, the size of j is 2*k+1.
Define dp[i][j] as the max profits we have on the ith day when the state is j, j=1 when the state is keeping a stock, j=0 when the state is not keeping any stock.
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2]).
Initialization: We can notice from LC 123 that if j is even, dp[0][j]=0 . If j is odd, dp[0][j]=-prices[0].
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [[0]*(2*k+1) for _ in range(length)]
for j in range(1, 2*k, 2):
dp[0][j] = -prices[0]
for i in range(1, length):
for j in range(0, 2*k-1, 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])
return dp[-1][2*k]
Optimize space complexity to O(1).
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [0]*(2*k+1)
for j in range(1, 2*k, 2):
dp[j] = -prices[0]
for i in range(1, length):
for j in range(1, 2*k+1):
if j % 2:
dp[j] = max(dp[j], dp[j-1]-prices[i])
else:
dp[j] = max(dp[j], dp[j-1]+prices[i])
return dp[-1]
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown
Key: You can complete as many transactions as you like, but you cannot hold multiple stocks at the same time, and after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Define dp[i][j] as the max money you have on the ith day with status j.
There are 4 states: j in {0,1,2,3}.
1: j=0: You buy one stock today or already bought one before.
You may already have a stock dp[i][0] = dp[i - 1][0]. You may buy a stock right after a cooldown day dp[i - 1][3] - prices[i]. You may buy a stock when you already passed a cooldown day for some days dp[i - 1][1] - prices[i]. Therefore dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]).
2: j=1: You don’t have any stock because you sold it one day before, and you passed the cooldown day. You may sold the stock the day before yesterday, and yesterday is the cooldown day dp[i - 1][3]. You may already passed the cooldown day dp[i - 1][1]. Therefore dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]).
3: j=2: You don’t have any stock because you sold it today. You must have a stock and sold it today dp[i][2] = dp[i - 1][0] + prices[i].
4: j=3: cooldown day. You sold your stock yesterday. dp[i][3] = dp[i - 1][2].
In summary, the recurrence relation for 4 status is
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
dp[i][2] = dp[i - 1][0] + prices[i]
dp[i][3] = dp[i - 1][2]
To initialize the base cases:
dp[0][0] = -prices[0] because you have bought one stock. dp[0][1] = 0 because you bought and sold one stock on the first day. dp[0][2]=0, dp[0][3]=0 the same.
Time complexity = Space complexity = O(n).
class Solution:
def maxProfit(self, prices: List[int]) -> int:
length = len(prices)
if length == 0: return 0
dp = [[0]*4 for _ in range(length)]
dp[0][0] = -prices[0]
for i in range(1, length):
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
dp[i][2] = dp[i - 1][0] + prices[i]
dp[i][3] = dp[i - 1][2]
return max(dp[-1][1],dp[-1][2],dp[-1][3])
LeetCode 714 Best Time to Buy and Sell Stock with Transaction Fee
Key: You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You must sell the stock before you buy again.
Define dp[i][0] as the max money you have on the ith day if you have a stock, dp[i][1] as the max money you have on the ith day if you don’t have a stock.
dp[i][0] comes from 1) dp[i - 1][0] if you have the stock the day before; 2) dp[i - 1][1] - prices[i] if you buy one stock on the ith day. Therefore dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]).
dp[i][1] comes from 1) dp[i-1][1] if you don’t have any stock the day before; 2) dp[i-1][0]+prices[i]-fee if you sell a stock today. Therefore, dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee).
Time complexity O(n). Space complexity O(n).
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
length = len(prices)
if length == 0: return 0
dp = [[0]*2 for _ in range(length)]
dp[0][0] = -prices[0]
for i in range(1, length):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
return max(dp[-1][0],dp[-1][1])
