Algorithms
Dynamic Programming (Intro)
Difficulty: Intermediate
Naive recursive Fibonacci computes fib(40) in seconds, fib(50) in minutes, and gives up on fib(60), all because it recomputes the same subproblems exponentially many times. Cache the result of each fib(k) the first time you compute it and...
Dynamic Programming (Intro)
Naive recursive Fibonacci computes fib(40) in seconds, fib(50) in minutes, and gives up on fib(60), all because it recomputes the same subproblems exponentially many times. Cache the result of each fib(k) the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming.
Dynamic Programming (Intro) turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does dp[i] represent?"), write the transition ("how does dp[i] follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops O(n) to O(1).
In Recursion Fundamentals, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately.
Next, Bit Manipulation (Intro) turns to a different toolkit, where bitwise operators give elegant O(1) solutions.
Prerequisites:
Recursion FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Identify the two properties (overlapping subproblems and optimal substructure) that make a problem suitable for dynamic programming.
Implement both top-down (memoization) and bottom-up (tabulation) approaches for Fibonacci and climbing stairs.
Define the DP state, transition formula, and base cases for coin change and house robber.
Optimize space by replacing a full DP table with rolling variables when only the last 1-2 states are needed.
Recognize DP problems by identifying patterns like 'count ways', 'minimum/maximum cost', and 'is it possible'.
Analyze the time and space complexity of DP solutions.
Why This Matters
01
Dynamic programming appears in 20-30% of medium and hard coding interview problems at top companies, making it the most frequently tested advanced algorithmic technique.
02
Memoization transforms exponential-time recursive solutions into polynomial-time solutions by caching overlapping subproblem results.
03
The DP mindset — defining state, transition, and base cases — transfers to problems across all domains: strings, arrays, trees, and graphs.
04
Space optimization techniques (rolling variables) reduce O(n) space to O(1), a common follow-up question in interviews.
Key Terms
8 terms you'll encounter in this lesson
Overlapping subproblems
A problem has overlapping subproblems when the same subproblems are solved multiple times during recursion. DP caches these results to avoid redundant computation.
Optimal substructure
A problem has optimal substructure when an optimal solution can be constructed from optimal solutions of its subproblems.
Memoization (top-down)
A technique that adds caching to a recursive function. The first call computes and stores the result; subsequent calls return the cached value. Works by recursive decomposition.
Tabulation (bottom-up)
An iterative approach that fills a DP table from the smallest subproblems up to the target problem. No recursion needed; avoids stack overflow for large inputs.
State
The parameters that uniquely define a subproblem. For climbing stairs, the state is the current step number. For coin change, the state is the remaining amount.
Transition
The recurrence relation that defines how to compute dp[i] from previously computed values. For Fibonacci: dp[i] = dp[i-1] + dp[i-2].
Base case
The smallest subproblem(s) whose answer is known without further recursion. For Fibonacci: dp[0] = 0, dp[1] = 1.
Space optimization
Reducing a DP table to only the values needed for the current transition. If dp[i] depends only on dp[i-1] and dp[i-2], we need only two variables instead of an array.
Heads Up
Common misconceptions to watch out for
"DP is just recursion with caching"
Memoization is recursion with caching, but bottom-up tabulation is purely iterative with no recursion at all. DP is the paradigm; memoization and tabulation are two implementation strategies.
"Every recursive problem benefits from DP"
DP only helps when there are overlapping subproblems. Problems like merge sort have independent subproblems (divide and conquer) — caching does not help because each subproblem is solved only once.
"Bottom-up is always better than top-down"
Bottom-up avoids recursion overhead and stack overflow risks, but top-down may be faster when only a subset of subproblems are actually needed (lazy evaluation). The choice depends on the problem structure.
"dp[i] always means the answer for input of size i"
The state definition varies by problem. dp[i] might represent the minimum coins for amount i, the number of ways to reach step i, or the maximum value using the first i items. Always start by clearly defining what dp[i] means.