54. Exemple DP 2 : Tabulation (Approche Bottom-Up)

La Tabulation est une technique de programmation dynamique ascendante (bottom-up). Au lieu de commencer par la solution souhaitée (N) et de la décomposer de manière récursive, nous partons du cas de base (0 ou 1) et construisons la solution de manière itérative à l'aide de boucles.

Exemple de Séquence de Fibonacci (Tabulation)

1. Initialiser un tableau (table) pour stocker les solutions des sous-problèmes, généralement jusqu'à la cible N.
2. Remplir les cas de base (par exemple, dp[0]=0, dp[1]=1).
3. Calculer itérativement les valeurs restantes en fonction des valeurs précédentes stockées.

python def fib_tabulation(n): if n <= 1: return n

dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1

# Iteratively build up the results
for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]
    
return dp[n]

La Tabulation évite souvent la surcharge d'appel de fonction de la récursivité, offrant parfois un petit avantage de vitesse sur la memoization.