Introduction to Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique used to solve complex problems by breaking them down into simpler subproblems, solving each subproblem exactly once, and storing their solutions to avoid redundant computations.

Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for the same inputs (overlapping subproblems), we can optimize it using DP to reduce the time complexity from exponential to polynomial.

Key Characteristics of DP Problems

A problem can be solved using Dynamic Programming if it has the following two properties:

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

Techniques to Solve DP Problems

There are two main approaches/methods to store values so that subproblem solutions can be reused:

Tabulation vs. Memoization

Here is a detailed comparison of the two approaches:

Basic Example: Factorial

Let's illustrate the difference using a simple factorial calculation (for educational purposes, though factorial doesn't have overlapping subproblems, it demonstrates the code structures):

1. Tabulation (Bottom-Up)

function factorialTabulation(n) {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1; // Base case
 
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] * i; // Bottom-up filling
    }
 
    return dp[n];
}

2. Memoization (Top-Down)

const dp = new Array(100).fill(-1);
 
function factorialMemoization(n) {
    if (n === 0) return 1; // Base case
 
    if (dp[n] !== -1) return dp[n]; // Return cached value
 
    dp[n] = n * factorialMemoization(n - 1); // Memoize and return
    return dp[n];
}