Dynamic Programming and Greedy for Beginners: A Step-by-Step Way to Thin
Gokul
· 7 min read
Dynamic programming has a reputation for being the hardest topic in placement prep, and most of that reputation comes from trying to memorize solutions instead of following a repeatable process. DP is really just recursion, plus reusing answers you have already worked out. Once you have a fixed way to approach any DP problem, the fear mostly goes away.
In short: define what a state means, write how it relates to smaller states, handle the base case, then fill states in the right order. Use greedy only when picking the best option right now never hurts you later.
Why DP Feels Hard
DP feels hard for three common reasons, and each one has a fix.
No fixed process: most learners jump straight to code without first defining what they are solving for.
Overlapping subproblems are invisible at first: plain recursion can recompute the same subproblem many times, and it is not always obvious where that happens.
The state is not obvious: deciding what “dp[i]” or “dp[i][j]” actually means is often the real difficulty, not the code around it.
The fix is the same every time: follow a structured approach instead of pattern-matching to a solution you memorized.
The 4-Step Approach
1. Define the state: decide exactly what a subproblem represents, such as “dp[i] is the minimum cost to reach step i”. Everything else follows from getting this right.
2. Write the transition: express the current state in terms of smaller states. This is usually the recursive relationship, written as a formula.
3. Handle the base case: identify the smallest input where the answer is obvious without any computation.
4. Decide the order: fill states so that whenever you compute one, everything it depends on is already known. This can be a simple loop, or explicit recursion with memoization.
Classic Example 1: Climbing Stairs
You can climb 1 or 2 steps at a time. How many distinct ways are there to reach the top of n stairs?
State:
dp[i]is the number of ways to reach step i.Transition: to reach step i, your last move was either 1 step from i-1, or 2 steps from i-2, so
dp[i] = dp[i-1] + dp[i-2].Base case:
dp[0] = 1(one way: do nothing),dp[1] = 1.Order: compute from i = 2 up to n, since each step needs the two before it.
Python
def climb_stairs(n):
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]Notice this is the Fibonacci sequence in disguise. Recognizing that pattern is one of the fastest ways to spot a DP problem.
Classic Example 2: 0/1 Knapsack
Given items with weights and values, and a bag with a weight limit, maximize the total value without exceeding the limit. Each item can be used at most once.
State:
dp[i][w]is the best value achievable using the first i items with capacity w.Transition: for each item, either skip it (
dp[i-1][w]) or take it if it fits (value[i] + dp[i-1][w-weight[i]]), and keep the larger of the two.Base case:
dp[0][w] = 0for all w, since with no items the best value is 0.Order: fill row by row, since row i depends only on row i-1.
Python
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # skip item i
if weights[i - 1] <= w:
dp[i][w] = max(
dp[i][w],
values[i - 1] + dp[i - 1][w - weights[i - 1]] # take item i
)
return dp[n][capacity]Classic Example 3: Longest Common Subsequence
Given two strings, find the length of their longest subsequence that appears in both, in the same relative order but not necessarily contiguous.
State:
dp[i][j]is the LCS length using the first i characters of string A and the first j characters of string B.Transition: if the characters at position i and j match,
dp[i][j] = 1 + dp[i-1][j-1]. Otherwise,dp[i][j] = max(dp[i-1][j], dp[i][j-1]).Base case:
dp[0][j] = dp[i][0] = 0, since an empty string has no common subsequence with anything.Order: fill row by row (or column by column), since each cell depends only on the row above and the column to the left.
Python
def lcs(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = 1 + dp[i - 1][j - 1]
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]Greedy vs DP, and How to Tell Them Apart
A greedy algorithm picks the option that looks best right now, and never reconsiders that choice. It is faster and simpler than DP, but it only gives the correct answer when a locally best choice never hurts you later, a property usually called the greedy choice property.
A practical way to decide: try the greedy approach on a small example by hand. If picking the locally best option ever leads you to a worse final answer than a different choice would have, greedy will not work, and you need DP instead.
Activity selection is a case where greedy works: always pick the activity that finishes earliest among the remaining valid options, since that leaves the most room for future activities. Knapsack is a case where greedy fails: picking the item with the best value first can leave you unable to fit a much better combination of smaller items later, so you need to consider combinations properly with DP.
Practice Problems
1. House Robber (DP)
You cannot rob two adjacent houses. Maximize the total amount robbed from a row of houses with given amounts.
State:
dp[i]is the max amount robbable from the first i houses.Transition: either skip house i (
dp[i-1]) or rob it and add to the best from two houses back (nums[i] + dp[i-2]), and take the larger.
Python
def rob(nums):
prev, curr = 0, 0
for num in nums:
prev, curr = curr, max(curr, prev + num)
return curr2. Coin Change (DP)
Given coin denominations and a target amount, find the minimum number of coins needed. This is a common trap for a greedy approach: greedy fails whenever the denominations do not divide evenly, so DP is required.
Python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -13. Activity Selection (Greedy)
Given activities with start and end times, select the maximum number that do not overlap. Sort by end time, then greedily pick each activity that starts after the last one picked ends.
Python
def activity_selection(activities):
# activities: list of (start, end)
activities.sort(key=lambda x: x[1]) # sort by end time
count, last_end = 0, float('-inf')
for start, end in activities:
if start >= last_end:
count += 1
last_end = end
return countKey Takeaways
DP is recursion plus reusing answers to subproblems you have already solved.
Follow the 4 steps in order: state, transition, base case, then order of computation.
Climbing stairs, knapsack and LCS cover the three most common DP shapes: 1D, 2D with a yes/no choice per item, and 2D over two sequences.
Greedy is faster but only correct when a locally best choice never costs you later. Test it by hand on a small example before trusting it.
When in doubt between greedy and DP, try to build a counterexample for greedy. If you find one, use DP.
Practice Recognizing These Patterns Under Time Pressure
Spotting whether a problem needs greedy or DP, and picking the right state, is a skill that improves with timed practice. Take a timed skill test on Skillrank to see how you do on DP and greedy questions under real test conditions.