| """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]) |
| |
| 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)) |
|
|
