Guide Programmation dynamique · 4/6
Ce chapitre n'est disponible qu'en anglais pour le moment.
Analyzing a DP is usually mechanical: count the states, count the work per state, and multiply. This chapter applies that rule to the classic problems, explains why knapsack is called pseudo-polynomial, compares memoization with tabulation, and shows how to cut memory with rolling arrays.
For Fibonacci there are n + 1 states and each does constant work, so time is O(n). For LCS there are (n + 1)(m + 1) states, each doing constant work, so time is O(nm). For coin change with k coin types, each of the amount + 1 states looks at k coins, giving O(amount x k).
| Problem | State | Time | Space (table) | Space (optimized) |
|---|---|---|---|---|
| Fibonacci | n | O(n) | O(n) | O(1) |
| Coin change (min coins) | amount | O(A x k) | O(A) | O(A) |
| 0/1 knapsack | item, capacity | O(n x W) | O(n x W) | O(W) |
| LCS / edit distance | i, j | O(n x m) | O(n x m) | O(min(n, m)) |
| LIS, simple DP | end index | O(n^2) | O(n) | O(n) |
| LIS, patience sorting | length | O(n log n) | O(n) | O(n) |
There is rarely a separate best or worst case for a DP: the table is filled completely regardless of the input values. Memoization can be faster in practice when only a fraction of the states is reachable from the starting state.
O(n x W) for knapsack looks polynomial, but W is a number, not the length of the input. Writing W takes only about log2(W) bits, so adding one more bit to the input can double the running time. Such algorithms are called pseudo-polynomial. The 0/1 knapsack problem is NP-hard in general; DP is practical only when capacities are reasonably small integers. When is huge but is tiny (say 40 items), meet-in-the-middle enumeration is often a better choice.
Wn| Aspect | Memoization (top-down) | Tabulation (bottom-up) |
|---|---|---|
| Code shape | Recursive function plus cache | Loops over a table |
| States computed | Only reachable ones | All of them |
| Order | Found automatically | You must choose it |
| Overhead | Function calls, hashing of arguments | Array indexing |
| Recursion depth | Can hit limits (Python default about 1000) | No recursion |
| Space optimization | Hard | Natural (rolling rows) |
In Python the recursion limit is the most common surprise. A memoized function on a chain of a few thousand states raises RecursionError, and sys.setrecursionlimit does not always help: recent Python versions also limit how deep calls may nest through C code, and the functools.cache wrapper is written in C. A simple workaround is to warm the cache from small to large, so every call finds its smaller states already stored.
from functools import cache
@cache
def ways(n: int) -> int:
"""Number of ways to climb n stairs with steps of 1 or 2."""
if n <= 1:
return 1
return ways(n - 1) + ways(n - 2)
try:
ways(5_000)
except RecursionError:
print("too deep")
for i in range(5_001): # warm up: each call recurses only one level
ways(i)
print(ways(5_000) % 1_000_000_007)
print(ways.cache_info().currsize) # 5001 states storedWarming up is really bottom-up evaluation in disguise. For tens of thousands of states, write the loop directly.
If a row of the table depends only on the previous row, you never need more than two rows at once. LCS length in O(min(n, m)) space:
def lcs_length(a: str, b: str) -> int:
if len(b) > len(a):
a, b = b, a # make b the shorter string
prev = [0] * (len(b) + 1)
for ch in a:
cur = [0] * (len(b) + 1)
for j, bj in enumerate(b, start=1):
cur[j] = prev[j - 1] + 1 if ch == bj else max(prev[j], cur[j - 1])
prev = cur
return prev[-1]
print(lcs_length("ABCBDAB", "BDCABA")) # 4The trade-off: with only two rows left, you can no longer walk the table backwards to reconstruct the subsequence. Hirschberg's algorithm recovers it in linear space with a divide-and-conquer trick, at roughly twice the time.
Sometimes a better state definition changes the complexity class. The simple LIS recurrence checks every earlier index, giving O(n^2). Keeping, for each length, the smallest possible tail value lets binary search replace the inner loop:
from bisect import bisect_left
def lis_length(nums: list[int]) -> int:
tails: list[int] = [] # tails[k] = smallest tail of an increasing run of length k + 1
for x in nums:
k = bisect_left(tails, x)
if k == len(tails):
tails.append(x)
else:
tails[k] = x
return len(tails)
print(lis_length([3, 1, 4, 1, 5, 9, 2, 6])) # 4, for example 1, 4, 5, 9tails stays sorted, so each element costs O(log n) and the total is O(n log n).
| Approach | Typical cost on knapsack-like problems | Correct? |
|---|---|---|
| Brute force over all subsets | O(2^n) | Yes, but only for small n |
| Greedy by value/weight ratio | O(n log n) | Not for 0/1 knapsack (correct for the fractional version) |
| Dynamic programming | O(n x W) | Yes, when W is small |
| Branch and bound | Exponential worst case, often fast | Yes |
W.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.