Documenting LeetCode solving.
Q106
Medium. 2D DP.
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# last row, is always filled with 1 (only right direction)
row = [1] * n
for i in range(m - 1):
newRow = [1] * n
# last column, is always filled with 1 (only down direction)
for j in range(n - 2, -1, -1):
# right + down paths
newRow[j] = newRow[j + 1] + row[j]
row = newRow
return row[0]
Q107
1143. Longest Common Subsequence
Medium. 2D DP.
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
# text2 as column
dp = [[0 for j in range(len(text2) + 1)] for i in range(len(text1) + 1)]
for i in range(len(text1) - 1, -1, -1):
for j in range(len(text2) - 1, -1, -1):
if text1[i] == text2[j]:
dp[i][j] = 1 + dp[i + 1][j + 1]
else:
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])
return dp[0][0]
