Dynamic Programming in C: Fibonacci, 0/1 Knapsack, LCS, Coin Change & Edit Distance with Code Examples

1. What is Dynamic Programming (DP)?

Dynamic Programming is a problem-solving technique that solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing results to avoid redundant computations. It’s used for optimization problems with optimal substructure and overlapping subproblems.

2. What are the key characteristics of DP problems?

3. What are common DP problems?

Fibonacci, Knapsack, Longest Common Subsequence (LCS), Coin Change, Edit Distance, Matrix Chain Multiplication, Shortest Path.

4. What are the approaches to implement DP?

5. What is Memoization?

Memoization is a top-down DP approach where a recursive function stores results of subproblems in a cache (e.g., array or hash table) to avoid recomputation. It’s intuitive but may use more stack space.

6. What is Tabulation?

Tabulation is a bottom-up DP approach where subproblems are solved iteratively and stored in a table, building the solution from smaller to larger subproblems. It’s typically more space-efficient and avoids recursion.

7. What are the differences between Memoization and Tabulation?

8. When to use Memoization vs. Tabulation?

9. What is the Fibonacci Sequence problem?

The Fibonacci Sequence problem involves computing the nth Fibonacci number, where each number is the sum of the two preceding ones (e.g., 0, 1, 1, 2, 3, 5, ...).

10. How is DP used in Fibonacci?

DP avoids recomputing Fibonacci numbers by storing results of subproblems, reducing time complexity from O(2^n) (naive recursion) to O(n).

11. Can you give an example of Fibonacci using Memoization in C?

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

long long memo[MAX];

void initMemo() {
    for (int i = 0; i < MAX; i++) memo[i] = -1;
}

long long fibMemo(int n) {
    if (n <= 1) return n; // Base case
    if (memo[n] != -1) return memo[n]; // Return cached result
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2); // Store and return
}

int main() {
    initMemo();
    printf("%lld\n", fibMemo(10)); // Output: 55
    return 0;
}

12. Can you give an example of Fibonacci using Tabulation in C?

#include <stdio.h>

long long fibTab(int n) {
    long long dp[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // Build bottom-up
    }
    return dp[n];
}

int main() {
    printf("%lld\n", fibTab(10)); // Output: 55
    return 0;
}

13. What is the time and space complexity of Fibonacci with DP?

Time Complexity: O(n) (both Memoization and Tabulation).

Space Complexity:

14. What is the 0/1 Knapsack problem?

Given items with weights and values, select a subset to maximize total value without exceeding a knapsack capacity, where each item can be chosen once (0/1).

15. How is DP used in Knapsack?

DP builds a table to store maximum values for subproblems defined by item count and capacity, choosing whether to include or exclude each item.

16. Can you give an example of 0/1 Knapsack using Tabulation in 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, n = 3;
    printf("%d\n", knapsack(W, wt, val, n)); // Output: 220
    return 0;
}

17. What is the time and space complexity of 0/1 Knapsack?

Time Complexity: O(n * W) (n = items, W = capacity).

Space Complexity: O(n * W) (dp table, can be optimized to O(W) with 1D array).

18. What is the Longest Common Subsequence problem?

Given two strings, LCS finds the longest subsequence (not necessarily contiguous) present in both strings (e.g., LCS of "ABCD" and "ACDF" is "ACD").

19. How is DP used in LCS?

DP builds a table to store lengths of LCS for prefixes of both strings, choosing whether to include a matching character or skip one string’s character.

20. Can you give an example of LCS using Tabulation in C?

#include <stdio.h>
#include <string.h>

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

int lcs(char* X, char* Y, int m, int n) {
    int dp[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) dp[i][j] = 0;
            else if (X[i - 1] == Y[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];
}

int main() {
    char X[] = "ABCD";
    char Y[] = "ACDF";
    int m = strlen(X), n = strlen(Y);
    printf("%d\n", lcs(X, Y, m, n)); // Output: 3 (for "ACD")
    return 0;
}

21. What is the time and space complexity of LCS?

Time Complexity: O(m * n) (m, n = lengths of strings).

Space Complexity: O(m * n) (dp table, can be optimized to O(min(m, n))).

22. What is the Coin Change problem?

Given a set of coin denominations and a target amount, find the minimum number of coins needed to make the amount (unlimited supply of coins).

23. How is DP used in Coin Change?

DP builds a table to store the minimum coins needed for each amount up to the target, choosing the minimum over all coin denominations.

24. Can you give an example of Coin Change using Tabulation in C?

#include <stdio.h>
#include <limits.h>

int minCoins(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) dp[i] = INT_MAX;
    
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                dp[i] = (dp[i] < dp[i - coins[j]] + 1) ? dp[i] : dp[i - coins[j]] + 1;
            }
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 5, 10, 25};
    int n = 4, amount = 30;
    printf("%d\n", minCoins(coins, n, amount)); // Output: 3 (25 + 5)
    return 0;
}

25. What is the time and space complexity of Coin Change?

Time Complexity: O(n * amount) (n = number of coins).

Space Complexity: O(amount) (dp array).

26. What is the Edit Distance problem?

Edit Distance (or Levenshtein Distance) finds the minimum number of operations (insert, delete, replace) to transform one string into another.

27. How is DP used in Edit Distance?

DP builds a table to store the minimum operations needed for prefixes of both strings, comparing characters and choosing the minimum operation.

28. Can you give an example of Edit Distance using Tabulation in C?

#include <stdio.h>
#include <string.h>

int min(int a, int b, int c) {
    return a < b ? (a < c ? a : c) : (b < c ? b : c);
}

int editDistance(char* str1, char* str2, int m, int n) {
    int dp[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) dp[i][j] = j; // Insert j characters
            else if (j == 0) dp[i][j] = i; // Delete i characters
            else if (str1[i - 1] == str2[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        }
    }
    return dp[m][n];
}

int main() {
    char str1[] = "sunday";
    char str2[] = "saturday";
    int m = strlen(str1), n = strlen(str2);
    printf("%d\n", editDistance(str1, str2, m, n)); // Output: 3
    return 0;
}

29. What is the time and space complexity of Edit Distance?

Time Complexity: O(m * n) (m, n = string lengths).

Space Complexity: O(m * n) (dp table, can be optimized to O(min(m, n))).