Dynamic Programming in C - Memoization, Tabulation

DP Basics

Dynamic Programming solves problems by breaking them into subproblems and storing results to avoid recomputation.

Two Approaches

Memoization (Top-Down) - Recursive with caching
Tabulation (Bottom-Up) - Iterative, fills table

When to Use DP

Overlapping subproblems
Optimal substructure

Fibonacci with DP

Memoization (Top-Down)

fib_memo.c

#include <stdio.h>
#define MAX 100

int memo[MAX];

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

int main() {
    for (int i = 0; i < MAX; i++) memo[i] = -1;
    printf("Fib(40) = %d\n", fibMemo(40));
    return 0;
}

Tabulation (Bottom-Up)

fib_tab.c

int fibTab(int n) {
    if (n <= 1) return 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];
}

0/1 Knapsack Problem

knapsack.c

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int knapsack(int W, int wt[], int 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];
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);
    
    printf("Maximum value: %d\n", knapsack(W, wt, val, n));
    return 0;
}