Multidimensional DP¶
Table of Contents¶
- 120. Triangle (Medium)
- 64. Minimum Path Sum (Medium)
- 63. Unique Paths II (Medium)
- 5. Longest Palindromic Substring (Medium)
- 97. Interleaving String (Medium)
- 72. Edit Distance (Medium)
- 123. Best Time to Buy and Sell Stock III (Hard)
- 188. Best Time to Buy and Sell Stock IV (Hard)
- 221. Maximal Square (Medium)
120. Triangle¶
from functools import cache
from typing import List
class Solution:
# Recursive
def minimumTotalRecursive(self, triangle: List[List[int]]) -> int:
n = len(triangle)
@cache
def dfs(i, j):
if i == n - 1:
return triangle[i][j]
return min(dfs(i + 1, j), dfs(i + 1, j + 1)) + triangle[i][j]
return dfs(0, 0)
# Iterative
def minimumTotalIterative(self, triangle: List[List[int]]) -> int:
for i in range(len(triangle) - 2, -1, -1):
for j in range(i + 1):
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
return triangle[0][0]
if __name__ == "__main__":
solution = Solution()
triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
assert solution.minimumTotalRecursive(triangle) == 11
assert solution.minimumTotalIterative(triangle) == 11
64. Minimum Path Sum¶
from functools import cache
from typing import List
# Iterative
def minPathSum(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
# init
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m):
dp[i][0] = grid[i][0] + dp[i - 1][0]
for j in range(1, n):
dp[0][j] = grid[0][j] + dp[0][j - 1]
# update
for i in range(1, m):
for j in range(1, n):
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
# Recursive
def minPathSumDFS(grid: List[List[int]]) -> int:
INF = 10**18
@cache
def dfs(i, j):
if i < 0 or j < 0:
return INF
if i == 0 and j == 0:
return grid[i][j]
return min(dfs(i, j - 1), dfs(i - 1, j)) + grid[i][j]
return dfs(len(grid) - 1, len(grid[0]) - 1)
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
print(minPathSum(grid)) # 7
print(minPathSumDFS(grid)) # 7
63. Unique Paths II¶
from functools import cache
from typing import List
class UniquePathsWithObstacles:
def memoization(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: DFS with Memoization
Time complexity: O(mn).
Space complexity: O(mn).
"""
@cache
def dfs(i: int, j: int) -> int:
if i < 0 or j < 0 or obstacleGrid[i][j]:
return 0
if i == 0 and j == 0:
return 1
return dfs(i - 1, j) + dfs(i, j - 1)
m, n = len(obstacleGrid), len(obstacleGrid[0])
return dfs(m - 1, n - 1)
def dp_2d(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: 2D Dynamic Programming
Time complexity: O(mn).
Space complexity: O(mn).
"""
# edge cases
if obstacleGrid[0][0] == 1 or obstacleGrid[-1][-1] == 1:
return 0
m, n = len(obstacleGrid), len(obstacleGrid[0])
# init dp
dp = [[0] * n for _ in range(m)]
for i in range(m):
if obstacleGrid[i][0] == 0:
dp[i][0] = 1
else:
break
for j in range(n):
if obstacleGrid[0][j] == 0:
dp[0][j] = 1
else:
break
# update dp
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 1:
continue
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]
def dp_1d(self, obstacleGrid: List[List[int]]) -> int:
"""
Approach: 1D Dynamic Programming
Time complexity: O(mn).
Space complexity: O(n).
"""
n = len(obstacleGrid[0])
dp = [0] * (n + 1)
dp[1] = 1
for row in obstacleGrid:
for j, x in enumerate(row):
if x == 0:
dp[j + 1] += dp[j]
else:
dp[j + 1] = 0
return dp[n]
if __name__ == "__main__":
solution = UniquePathsWithObstacles()
obstacleGrid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
assert solution.dp_2d(obstacleGrid) == 2
assert solution.memoization(obstacleGrid) == 2
assert solution.dp_1d(obstacleGrid) == 2
5. Longest Palindromic Substring¶
"""
- Return the longest palindromic substring in `s`.
"""
# DP - Interval
def longestPalindromeDP(s: str) -> str:
n = len(s)
if n <= 1:
return s
start, maxLen = 0, 1
# Init
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for j in range(1, n):
for i in range(j):
if s[i] == s[j]:
if j - i <= 2:
dp[i][j] = 1
else:
dp[i][j] = dp[i + 1][j - 1]
if dp[i][j] and j - i + 1 > maxLen:
maxLen = j - i + 1
start = i
return s[start : start + maxLen]
# Expand Around Center
def longestPalindromeCenter(s: str) -> str:
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
if len(s) <= 1:
return s
start, end = 0, 0
for i in range(len(s)):
len1 = expand_around_center(i, i) # odd
len2 = expand_around_center(i, i + 1) # even
maxLen = max(len1, len2)
if maxLen > end - start:
start = i - (maxLen - 1) // 2
end = i + maxLen // 2
return s[start : end + 1]
s = "babad"
print(longestPalindromeDP(s)) # "bab"
print(longestPalindromeCenter(s)) # "aba"
97. Interleaving String¶
# DP - 2D
def isInterleaveDP(s1: str, s2: str, s3: str) -> bool:
m, n, k = len(s1), len(s2), len(s3)
if m + n != k:
return False
dp = [[False] * (n + 1) for _ in range(m + 1)]
dp[0][0] = True
for i in range(1, m + 1):
dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
for j in range(1, n + 1):
dp[0][j] = dp[0][j - 1] and s2[j - 1] == s3[j - 1]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]) or (
dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
)
return dp[m][n]
# DFS
def isInterleaveDFS(s1: str, s2: str, s3: str) -> bool:
memo = {}
def dfs(i, j, k):
if i == len(s1) and j == len(s2) and k == len(s3):
return True
if (i, j) in memo:
return memo[(i, j)]
res = False
if i < len(s1) and k < len(s3) and s1[i] == s3[k]:
res |= dfs(i + 1, j, k + 1)
if j < len(s2) and k < len(s3) and s2[j] == s3[k]:
res |= dfs(i, j + 1, k + 1)
memo[(i, j)] = res
return res
return dfs(0, 0, 0)
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
print(isInterleaveDP(s1, s2, s3)) # False
print(isInterleaveDFS(s1, s2, s3)) # False
72. Edit Distance¶
from functools import cache
# Recursive
def minDistanceDFS(word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
@cache
def dfs(i: int, j: int) -> int:
if i < 0:
return j + 1
if j < 0:
return i + 1
if word1[i] == word2[j]:
return dfs(i - 1, j - 1)
return 1 + min(dfs(i - 1, j), dfs(i, j - 1), dfs(i - 1, j - 1))
return dfs(n - 1, m - 1)
# Iterative
def minDistanceDP(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] # no operation
else:
dp[i][j] = 1 + min(
dp[i - 1][j], # delete
dp[i][j - 1], # insert
dp[i - 1][j - 1], # replace
)
return dp[-1][-1]
if __name__ == "__main__":
word1 = "horse"
word2 = "ros"
print(minDistanceDFS(word1, word2)) # 3
print(minDistanceDP(word1, word2)) # 3
123. Best Time to Buy and Sell Stock III¶
from typing import List
# 1. DP
def maxProfitDP1(prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[0] * 5 for _ in range(n)]
dp[0][0] = 0 # no transaction
dp[0][1] = -prices[0] # buy 1
dp[0][2] = 0 # sell 1
dp[0][3] = -prices[0] # buy 2
dp[0][4] = 0 # sell 2
for i in range(1, n):
dp[i][0] = dp[i - 1][0]
dp[i][1] = max(dp[i - 1][1], -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]
# 2. DP - Optimized
def maxProfitDP2(prices: List[int]) -> int:
b1, b2 = float("inf"), float("inf")
s1, s2 = 0, 0
for price in prices:
b1 = min(b1, price)
s1 = max(s1, price - b1)
b2 = min(b2, price - s1)
s2 = max(s2, price - b2)
return s2
prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(maxProfitDP1(prices)) # 6
print(maxProfitDP2(prices)) # 6
188. Best Time to Buy and Sell Stock IV¶
from typing import List
# DP
def maxProfit(k: int, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[0] * (2 * k + 1) for _ in range(n)]
for j in range(1, 2 * k, 2):
dp[0][j] = -prices[0]
for i in range(1, n):
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]
k = 2
prices = [2, 4, 1]
print(maxProfit(k, prices)) # 2