Dynamic Programming

Dynamic Programming

# DP = recursion + memoisation (or tabulation)
# Use when: overlapping subproblems + optimal substructure

# 1. Fibonacci (classic intro)
# Top-down
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n): return n if n<=1 else fib(n-1)+fib(n-2)

# Bottom-up O(n) time O(1) space
def fib_tab(n):
    a, b = 0, 1
    for _ in range(n): a, b = b, a+b
    return a

# 2. Longest Common Subsequence
def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[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]

# 3. 0/1 Knapsack
def knapsack(weights, values, W):
    n  = len(weights)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for w in range(W+1):
            dp[i][w] = dp[i-1][w]
            if weights[i-1]<=w:
                dp[i][w] = max(dp[i][w], values[i-1]+dp[i-1][w-weights[i-1]])
    return dp[n][W]