Dynamic Programming: From Basics to Advanced

Dynamic Programming (DP) transforms exponential-time problems into polynomial-time solutions by avoiding redundant calculations through memoization or tabulation.

What is Dynamic Programming?

DP is applicable when:

• Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems
• Overlapping Subproblems: Same subproblems are solved multiple times

Memoization vs Tabulation

Memoization (Top-Down)

// Fibonacci with Memoization
int memo[100];
memset(memo, -1, sizeof(memo));

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

Tabulation (Bottom-Up)

// Fibonacci with Tabulation
int fib(int n) {
    int dp[n+1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

Classic DP Problems

1. Longest Common Subsequence

int lcs(string a, string b) {
    int n = a.size(), m = b.size();
    int dp[n+1][m+1];
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) dp[i][j] = 0;
            else 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[n][m];
}

2. 0/1 Knapsack

int knapsack(int W, vector& wt, vector& val, int n) {
    int dp[n+1][W+1];
    
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) dp[i][w] = 0;
            else if (wt[i-1] <= w)
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w]);
            else
                dp[i][w] = dp[i-1][w];
        }
    }
    return dp[n][W];
}

Problem-Solving Strategy

1. Define the state clearly
2. Identify the base cases
3. Write the recurrence relation
4. Determine the order of computation
5. Optimize space if needed

Back to Portfolio