Foundation drill for this topic
Medium Grid DP
In plain English: Count the number of ways to walk from the top-left to the bottom-right of a grid, only moving right or down.
dp[i][j] = number of ways to reach cell (i,j). Each cell can only come from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. Optimize to a single row since we only look at the previous row.
Prompt
A robot is in the top-left corner of an m x n grid. It can only move right or down. How many unique paths are there to the bottom-right corner?
Try to write it from scratch before scrolling down.
Solution
def unique_paths(m, n):
row = [1] * n # base: top row all 1s
for i in range(1, m):
for j in range(1, n):
row[j] += row[j-1] # above + left
return row[-1]
# Test: unique_paths(3, 7) == 28
# Test: unique_paths(3, 2) == 3Quick recall drills to reinforce this pattern.
Sortedness check is a precondition guard for binary search and merge operations.
all(a[i] <= a[i+1] for i in range(len(a)-1))Transpose + reverse-rows rotates 90 degrees clockwise in-place. Classic matrix manipulation.
n = len(m)
for i in range(n):
for j in range(i+1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
row.reverse()Backtracking on tree: append node, recurse, pop. Collect path copy at valid leaves. Classic tree + backtrack combo.
def pathSum(root, targetSum):
res = []
def dfs(node, remaining, path):
if not node: return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
res.append(path[:]) # copy!
dfs(node.left, remaining - node.val, path)
dfs(node.right, remaining - node.val, path)
path.pop() # backtrack
dfs(root, targetSum, [])
return res