Mastering Dynamic Programming

Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them down into simpler subproblems. It is applicable when subproblems overlap recursively, allowing us to cache results and avoid redundant work.

Top-Down (Memoization) vs Bottom-Up (Tabulation)

Top-Down DP starts with the main problem and recursively breaks it down, storing solved subproblem states in a dictionary or array (memo). Bottom-Up DP starts from the base cases and iteratively fills up a state table (tabulation).

// Coin Change: Bottom-Up Tabulation O(N * amount)
function coinChange(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

The 3 Steps to Solve Any DP Problem

• Define the state: What do the DP table indices represent? (e.g., dp[i] is the minimum coins to make amount i).
• Formulate the recurrence relation: How does the current state relate to previous states? (e.g., dp[i] = min(dp[i - coin] + 1)).
• Identify base cases: What are the simplest states that require no calculation? (e.g., dp[0] = 0).