File size: 3,851 Bytes
1797f2f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | """Programmation dynamique — algorithmes DP vérifiables — vague 3.
DP : sous-problèmes + mémoïsation/tabulation. Algorithmes classiques EXACTS :
* Sac à dos (0/1 knapsack) : valeur max sous contrainte de poids.
* Plus longue sous-séquence commune (LCS) : alignement de séquences.
* Distance d'édition (Levenshtein) : nb minimal d'opérations.
* Fibonacci mémoïsé, plus court chemin (Bellman-Ford), sous-séquence croissante (LIS).
Vérifiable : résultats exacts (ground truth connu).
"""
from __future__ import annotations
from typing import List, Tuple
def knapsack(weights: List[int], values: List[int], capacity: int) -> int:
"""Sac à dos 0/1 : valeur max. DP tabulaire. O(n·capacity)."""
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w]
if weights[i - 1] <= w:
dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
def lcs(a: str, b: str) -> int:
"""Longueur de la plus longue sous-séquence commune."""
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
def lcs_sequence(a: str, b: str) -> str:
"""La sous-séquence commune elle-même (reconstruction)."""
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# reconstruction
i, j, res = m, n, []
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]:
res.append(a[i - 1]); i -= 1; j -= 1
elif dp[i - 1][j] > dp[i][j - 1]:
i -= 1
else:
j -= 1
return "".join(reversed(res))
def edit_distance(a: str, b: str) -> int:
"""Distance de Levenshtein (insertion/suppression/substitution)."""
m, n = len(a), len(b)
dp = list(range(n + 1))
for i in range(1, m + 1):
prev = dp[0]; dp[0] = i
for j in range(1, n + 1):
cur = dp[j]
cost = 0 if a[i - 1] == b[j - 1] else 1
dp[j] = min(dp[j] + 1, dp[j - 1] + 1, prev + cost)
prev = cur
return dp[n]
def longest_increasing_subsequence(arr: List[int]) -> int:
"""Plus longue sous-séquence strictement croissante."""
if not arr:
return 0
dp = [1] * len(arr)
for i in range(len(arr)):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def coin_change(coins: List[int], amount: int) -> int:
"""Nb minimal de pièces pour faire 'amount'. -1 si impossible."""
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return dp[amount] if dp[amount] != float("inf") else -1
if __name__ == "__main__":
print("[dp] knapsack([2,3,4,5],[3,4,5,6],cap=5) =", knapsack([2, 3, 4, 5], [3, 4, 5, 6], 5))
print("[dp] LCS('ABCBDAB','BDCAB') =", lcs("ABCBDAB", "BDCAB"),
"| séquence:", lcs_sequence("ABCBDAB", "BDCAB"))
print("[dp] edit_distance('kitten','sitting') =", edit_distance("kitten", "sitting"), "(=3)")
print("[dp] LIS([10,9,2,5,3,7,101,18]) =", longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))
print("[dp] coin_change([1,5,10],27) =", coin_change([1, 5, 10], 27))
|