Guide Programmation dynamique · 5/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
These five problems were written for this guide. Try each one before reading the approach: write down the state, the recurrence, the base cases and the order first, then code it. All solutions run with Python 3.9 or later.
A staircase has n steps. You start on step 0 and may climb 1, 2 or 3 steps at a time, but some steps are broken and cannot be stepped on. How many different ways are there to reach step n? Return the count modulo 1_000_000_007.
Example: with n = 4 and step 2 broken, the valid routes are 0-1-4, 0-3-4 and 0-1-3-4, so the answer is 3. Routes such as 0-2-4 or 0-1-2-3-4 are invalid because they touch step 2.
Approach: ways[i] = number of ways to stand on step i. Broken steps have 0 ways; otherwise ways[i] = ways[i-1] + ways[i-2] + ways[i-3]. Base case ways[0] = 1.
MOD = 1_000_000_007
def count_climbs(n: int, broken: set[int]) -> int:
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
if i in broken:
continue
ways[i] = sum(ways[i - s] for s in (1, 2, 3) if i - s >= 0) % MOD
return ways[n]
print(count_climbs(4, {2})) # 3
print(count_climbs(30, set())) # 53798080A warehouse floor is a grid of tolls. A robot starts at the top-left cell and must reach the bottom-right cell, moving only right or down, paying the toll of every cell it enters (including the first). Find the minimum total toll.
Approach: cost[r][c] = cheapest total to arrive at cell (r, c). Each cell is reached from above or from the left, so cost[r][c] = grid[r][c] + min(above, left). A single row suffices because each row only needs the row above.
def cheapest_route(grid: list[list[int]]) -> int:
cols = len(grid[0])
row = [0] * cols
for r, line in enumerate(grid):
for c, toll in enumerate(line):
if r == 0 and c == 0:
row[c] = toll
elif r == 0:
row[c] = row[c - 1] + toll
elif c == 0:
row[c] = row[c] + toll
else:
row[c] = min(row[c], row[c - 1]) + toll
return row[-1]
print(cheapest_route([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # 7A search box wants to suggest the closest product name to what a user typed. Define the distance between two words as the fewest single-character insertions, deletions or substitutions needed to turn one into the other (Levenshtein distance). Compute it.
Approach: d[i][j] = distance between the first i characters of s and the first of . If the characters match, ; otherwise it is 1 plus the minimum of delete (), insert () and substitute (). Base cases: , .
jtd[i][j] = d[i-1][j-1]d[i-1][j]d[i][j-1]d[i-1][j-1]d[i][0] = id[0][j] = jdef edit_distance(s: str, t: str) -> int:
prev = list(range(len(t) + 1))
for i, a in enumerate(s, start=1):
cur = [i] + [0] * len(t)
for j, b in enumerate(t, start=1):
if a == b:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
print(edit_distance("keybaord", "keyboard")) # 2
print(edit_distance("kitten", "sitting")) # 3A team won several prizes with integer values. Can they be divided into two groups with exactly equal total value?
Approach: if the total is odd, the answer is no. Otherwise ask whether some subset sums to total // 2. That is a 0/1 knapsack with booleans: can[s] is true when some subset of the items seen so far sums to s. Iterate sums from high to low so each prize is used once.
def can_split_evenly(prizes: list[int]) -> bool:
total = sum(prizes)
if total % 2:
return False
target = total // 2
can = [True] + [False] * target
for p in prizes:
for s in range(target, p - 1, -1):
can[s] = can[s] or can[s - p]
return can[target]
print(can_split_evenly([3, 1, 5, 9, 4])) # False (total 22, no subset sums to 11)
print(can_split_evenly([3, 1, 5, 9, 2])) # True (9 + 1 = 3 + 5 + 2)Given daily temperatures, find the longest sequence of days (not necessarily consecutive) on which each day was strictly warmer than the previous chosen day, and return one such sequence.
Approach: the O(n^2) LIS is easy to reconstruct. length[i] is the longest increasing subsequence ending at day i, and parent[i] remembers the previous day in that subsequence.
def warming_streak(temps: list[int]) -> list[int]:
if not temps:
return []
n = len(temps)
length = [1] * n
parent = [-1] * n
for i in range(n):
for j in range(i):
if temps[j] < temps[i] and length[j] + 1 > length[i]:
length[i] = length[j] + 1
parent[i] = j
i = max(range(n), key=length.__getitem__)
streak = []
while i != -1:
streak.append(temps[i])
i = parent[i]
return streak[::-1]
print(warming_streak([12, 9, 14, 10, 15, 11, 18, 13])) # [12, 14, 15, 18]For long inputs, combine the bisect version from the complexity chapter with an index array to reconstruct in O(n log n).
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.