Dynamic Programming: Tree Traversals, Stock Trading, and Subsequence Problems
1. House Robber III (Binary Tree)
Given a binary tree representing houses where each node has a value. Adjacent houses (parenet and child) cannot both be robbed on the same night. Determine the maximum amount that can be robbed without triggering an alarm.
State Definition:
For each node, we track two states: not_robbed[i] represents the maximum value when this node is not robbed, and robbed[i] represents the maximum value when this node is robbed.
Approach:
Use post-order traversal (left-right-center) to compute values from bottom to top. For any node: if not robbed, children can be either robbed or not; if robbed, children cannot be robbed.
Python Implementation:
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
class Solution:
def rob(self, root: TreeNode) -> int:
result = self.helper(root)
return max(result[0], result[1])
def helper(self, node):
if node is None:
return [0, 0]
left_result = self.helper(node.left)
right_result = self.helper(node.right)
skip = max(left_result[0], left_result[1]) + max(right_result[0], right_result[1])
take = node.val + left_result[0] + right_result[0]
return [skip, take]
Stock Trading Problems
2. Best Time to Buy and Sell Stock (Single Transaction)
Find the maximum profit with at most one buy and one sell transaction.
Greedy Solution:
class Solution:
def maxProfit(self, prices: list[int]) -> int:
lowest_price = float('inf')
max_profit = 0
for price in prices:
if price < lowest_price:
lowest_price = price
elif price - lowest_price > max_profit:
max_profit = price - lowest_price
return max_profit
Dynamic Programming Solution:
dp[i][0] = max profit on day i without holding stock
dp[i][1] = max profit on day i holding stock
class Solution:
def maxProfit(self, prices: list[int]) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
return max(dp[n-1][0], dp[n-1][1])
3. Best Time to Buy and Sell Stock II (Unlimited Transactions)
Allow multiple buy-sell transactions. Greedy accumulates all positive differences.
class Solution:
def maxProfit(self, prices: list[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
DP Solution:
class Solution:
def maxProfit(self, prices: list[int]) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0, 0] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1, n):
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 max(dp[n-1][0], dp[n-1][1])
4. Best Time to Buy and Sell Stock III (At Most Two Transactions)
Five states are needed: no operation, first buy, first sell, second buy, second sell.
class Solution:
def maxProfit(self, prices: list[int]) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0] * 5 for _ in range(n)]
# Initialization
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[0][2] = 0
dp[0][3] = -prices[0]
dp[0][4] = 0
for i in range(1, n):
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[n-1][4]
5. Best Time to Buy and Sell Stock IV (K Transactions)
Generalize the two-transaction solution to k transactions. Total states = 2k + 1.
class Solution:
def maxProfit(self, k: int, prices: list[int]) -> int:
if not prices:
return 0
n = len(prices)
if k > n // 2:
# Convert to unlimited transactions
profit = 0
for i in range(1, n):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
dp = [[0] * (2 * k + 1) for _ in range(n)]
# Initialize first day
dp[0][0] = 0
for i in range(1, 2 * k + 1):
if i % 2 == 1:
dp[0][i] = -prices[0]
else:
dp[0][i] = 0
# Fill DP table
for i in range(1, n):
dp[i][0] = dp[i-1][0]
for j in range(1, 2 * k + 1):
if j % 2 == 1:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])
else:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])
return dp[n-1][2 * k]
6. Best Time to Buy and Sell Stock with Cooldown
After selling, one day of cooldown is required before buying again. Four states: hold, not hold, just sold, cooldown.
class Solution:
def maxProfit(self, prices: list[int]) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0] * 4 for _ in range(n)]
dp[0][0] = -prices[0] # Holding stock
dp[0][1] = 0 # Not holding, not in cooldown
dp[0][2] = 0 # Just sold
dp[0][3] = 0 # Cooldown
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] - 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[n-1][1], dp[n-1][2], dp[n-1][3])
7. Best Time to Buy and Sell Stock with Transaction Fee
Pay transaction fee for each completed transaction.
class Solution:
def maxProfit(self, prices: list[int], fee: int) -> int:
if not prices:
return 0
n = len(prices)
dp = [[0] * 2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
return dp[n-1][0]
Stock Problem Summary
Subsequence Problems
8. Longest Increasing Subsequence
Find the length of the longest strictly increasing subsequence.
dp[i] = length of LIS ending at index i
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1] * n
max_length = 1
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
max_length = max(max_length, dp[i])
return max_length
9. Longest Continuous Increasing Subsequence
Subsequence must be contiguous. Single pass suffices.
class Solution:
def findLengthOfLCIS(self, nums: list[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1] * n
max_length = 1
for i in range(1, n):
if nums[i] > nums[i-1]:
dp[i] = dp[i-1] + 1
max_length = max(max_length, dp[i])
return max_length
10. Maximum Length of Repeated Subarray
Find the longest common subarray between two arrays (must be contiguous).
class Solution:
def findLength(self, nums1: list[int], nums2: list[int]) -> int:
len1, len2 = len(nums1), len(nums2)
max_len = 0
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
return max_len
11. Longest Common Subsequence
Subsequence need not be contiguous. Compare with subarray version.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
len1, len2 = len(text1), len(text2)
dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
max_len = 0
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
max_len = max(max_len, dp[i][j])
return max_len
12. Maximum Subarray
Greedy Approach:
class Solution:
def maxSubArray(self, nums: list[int]) -> int:
max_sum = float('-inf')
current_sum = 0
for num in nums:
if current_sum < 0:
current_sum = num
else:
current_sum += num
max_sum = max(max_sum, current_sum)
return max_sum
Dynamic Programming Approach:
dp[i] = maximum subarray sum ending at index i
class Solution:
def maxSubArray(self, nums: list[int]) -> int:
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
max_sum = nums[0]
for i in range(1, n):
dp[i] = max(dp[i-1] + nums[i], nums[i])
max_sum = max(max_sum, dp[i])
return max_sum
13. Is Subsequence
Two-Pointer Solution:
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
s_len, t_len = len(s), len(t)
if s_len > t_len:
return False
s_ptr, t_ptr = 0, 0
while t_ptr < t_len:
if s_ptr < s_len and t[t_ptr] == s[s_ptr]:
s_ptr += 1
t_ptr += 1
return s_ptr == s_len
DP Solution: Compute LCS length and check if it equals |s|.
14. Number of Distinct Subsequences
Count how many times string t appears as a subsequence in string s.
dp[i][j] = number of ways t[0..j-1] appears in s[0..i-1]
class Solution:
def numDistinct(self, s: str, t: str) -> int:
s_len, t_len = len(s), len(t)
dp = [[0] * (t_len + 1) for _ in range(s_len + 1)]
for i in range(s_len + 1):
dp[i][0] = 1
for i in range(1, s_len + 1):
for j in range(1, t_len + 1):
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[s_len][t_len]
