Dynamic Programming in C

Introduction to Dynamic Programming

Dynamic Programming (DP) is a powerful technique for solving problems that can be broken down into simpler sub-problems. It is particularly useful for optimization problems where we need to find the best solution among many possible solutions.

DP is based on two main principles:

• Overlapping Subproblems: The problem can be broken down into smaller, overlapping subproblems.
• Optimal Substructure: The optimal solution to the problem can be constructed from the optimal solutions of its subproblems.

Top-Down vs Bottom-Up Approaches

There are two main approaches to implement dynamic programming: Top-Down and Bottom-Up.

Top-Down Approach

In the top-down approach, we solve the problem by breaking it down recursively and storing the results of solved subproblems to avoid redundant computations. This is also known as memoization.

Bottom-Up Approach

In the bottom-up approach, we solve the problem by solving all possible subproblems first and then combining them to solve the overall problem. This usually involves using an iterative approach and filling up a table (array) to store the results of subproblems.

Example: Fibonacci Sequence

Let's take the Fibonacci sequence as an example to demonstrate both the top-down and bottom-up approaches.

Top-Down Approach (Memoization)

#include <stdio.h>

#define MAX 100

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

int main() {
    int n = 10;
    int memo[MAX];
    for (int i = 0; i < MAX; i++) memo[i] = -1;
    printf("Fibonacci of %d: %d\n", n, fib(n, memo));
    return 0;
}
                

Bottom-Up Approach (Tabulation)

#include <stdio.h>

int fib(int n) {
    int f[n+1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

int main() {
    int n = 10;
    printf("Fibonacci of %d: %d\n", n, fib(n));
    return 0;
}
                

Example: 0/1 Knapsack Problem

The 0/1 Knapsack problem is another classic example where dynamic programming can be applied. The problem is defined as follows:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Bottom-Up Approach (Tabulation)

#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 K[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                K[i][w] = 0;
            } else if (wt[i-1] <= w) {
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
            } else {
                K[i][w] = K[i-1][w];
            }
        }
    }
    return K[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 in Knapsack = %d\n", knapSack(W, wt, val, n));
    return 0;
}
                

Conclusion

Dynamic Programming is a powerful tool for solving complex problems that can be broken down into simpler subproblems. By using either the top-down or bottom-up approach, we can efficiently solve problems that would otherwise be computationally expensive.

In this tutorial, we have covered the basics of dynamic programming, including the principles of overlapping subproblems and optimal substructure, and demonstrated how to apply these principles using examples like the Fibonacci sequence and the 0/1 Knapsack problem.