Dynamic Programming Tutorial in C++

Introduction

Dynamic Programming (DP) is an optimization technique used to solve complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure.

Key Concepts

There are two key attributes that a problem must have to be solved using dynamic programming:

• Overlapping Subproblems: The problem can be broken down into smaller subproblems which are reused multiple times.
• Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions of its subproblems.

Approach

There are two main approaches to dynamic programming:

• Top-Down Approach (Memoization): Start solving the problem from the top and break it down into subproblems. Store the results of these subproblems to avoid recomputation.
• Bottom-Up Approach (Tabulation): Start solving the problem from the simplest subproblems and build up the final solution.

Example Problem: Fibonacci Numbers

The Fibonacci sequence is a classic example of a problem that can be solved using dynamic programming. The sequence is defined as follows:

Top-Down Approach (Memoization)

In the top-down approach, we start solving the problem from the top and use a memoization table to store the results of subproblems to avoid recomputation.

#include <iostream>
using namespace std;

const int MAX = 1000;
int memo[MAX];

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

int main() {
    for (int i = 0; i < MAX; ++i) memo[i] = -1;
    int n = 10;
    cout << "Fibonacci of " << n << " is " << fib(n) << endl;
    return 0;
}
                

Bottom-Up Approach (Tabulation)

In the bottom-up approach, we solve the problem by solving all the subproblems first and use their results to build up the solution to the original problem.

#include <iostream>
using namespace std;

int fib(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];
}

int main() {
    int n = 10;
    cout << "Fibonacci of " << n << " is " << fib(n) << endl;
    return 0;
}
                

Common Dynamic Programming Problems

Here are some commonly solved problems using dynamic programming:

• 0/1 Knapsack Problem
• Longest Common Subsequence (LCS)
• Longest Increasing Subsequence (LIS)
• Matrix Chain Multiplication
• Subset Sum Problem
• Coin Change Problem

Conclusion

Dynamic Programming is a powerful technique for solving optimization problems. By breaking problems down into simpler subproblems and storing their results to avoid recomputation, DP can significantly reduce the time complexity of problems with overlapping subproblems and optimal substructure. Both top-down and bottom-up approaches have their own advantages and can be used based on the context of the problem.