Dynamic Programming • Fundamentals

Introduction to DP

Master the core concepts of Overlapping Subproblems and Optimal Substructure that define Dynamic Programming.

What is DP?

Dynamic Programming is just an optimization over plain recursion. Whenever we see a recursive solution that repeatedly solves the same problems, we can optimize it using DP.

Overlapping Subproblems

Like in Fibonacci, where Fib(2) is called multiple times. If we store the result of Fib(2) the first time, we never have to compute it again.

Optimal Substructure

A problem has optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems. (e.g., Shortest Path).

Top-Down vs Bottom-Up

Top-Down uses recursion + a memoization hash map. Bottom-Up uses iteration + a DP table (array). Both achieve the same time complexity.

F(4)

Code Tracker

:::

1// Top-Down (Memoization)

2let memo = {};

3function fib(n) {

4 if (n <= 1) return n;

5 if (memo[n]) return memo[n];

6 return memo[n] = fib(n - 1) + fib(n - 2);

7}

8

9// Bottom-Up (Tabulation)

10let dp = [0, 1];

11for(let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];

Introduction To Dynamic Programming

Introduction To Dynamic Programming

Introduction to DP

What is DP?

Overlapping Subproblems

Optimal Substructure

Top-Down vs Bottom-Up

Introduction to DP

What is DP?

Overlapping Subproblems

Optimal Substructure

Top-Down vs Bottom-Up