Ugenz Academy/Tutorial

Dynamicprogramming

20 min read3,824 words

Reading progress

Keep learning

Dynamic Programming (DP)

Dynamic Programming (DP) is one of the most important problem-solving techniques in DSA.

It is mainly used when a problem can be broken into smaller subproblems, and the same subproblems are solved again and again.

The key idea is:

Solve each subproblem once, store its answer, and reuse it whenever needed.

1. Why Do We Need Dynamic Programming?

Let's start with a simple example: Fibonacci numbers.

The Fibonacci sequence is:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Formula:

F(n) = F(n-1) + F(n-2)

A simple recursive implementation:

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

Suppose we calculate:

fib(5)

The recursion looks like:

fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ fib(2) fib(1)

Notice something important:

fib(3)

is calculated multiple times.

And:

fib(2)

is also calculated multiple times.

This is repeated work.

Dynamic Programming eliminates this repeated work.

2. The Core Idea of DP

Without DP:

Calculate ↓ Calculate same thing again ↓ Calculate same thing again ↓ Waste time

With DP:

Calculate subproblem ↓ Store answer ↓ Need it again? ↓ Use stored answer

So:

DP = Recursion/Iteration + Storing Results

But this is a simplified mental model. DP specifically applies when the problem has the right structure, especially overlapping subproblems and optimal substructure.

3. Two Important Properties of DP

Before deciding whether a problem can use DP, look for two properties.

1. Overlapping Subproblems

The same smaller problem appears multiple times.

Example:

F(5) ├── F(4) │ ├── F(3) │ └── F(2) │ └── F(3) ├── F(2) └── F(1)

F(3) and F(2) are repeated.

This is:

Overlapping Subproblems

2. Optimal Substructure

The optimal answer to a larger problem can be constructed from optimal answers to its smaller subproblems.

For example, in some shortest-path and knapsack problems:

Optimal big solution ↓ Optimal smaller solutions

This property is essential for many optimization DP problems.

4. DP vs Divide and Conquer

You just studied Divide and Conquer.

They look similar, but there is an important difference.

Divide and Conquer

Subproblems are generally independent.

Problem / \ A B

You solve A and B separately.

Examples:

  • Merge Sort
  • Quick Sort
  • Binary Search

Dynamic Programming

Subproblems often overlap.

Problem / \ A B \ / C

Both A and B may need the answer to C.

Instead of calculating C twice:

Calculate C ↓ Store C ↓ Reuse C

That's the major difference.

5. The Two Approaches to DP

There are two main ways to implement Dynamic Programming:

  1. Top-Down DP
  2. Bottom-Up DP

6. Top-Down DP — Memoization

Top-down means:

Start with the original problem and recursively break it down.

Then store the answers of subproblems.

This technique is called Memoization.

Example: Fibonacci

Normal recursion:

int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }

Now add a DP array.

int fib(int n, vector<int>& dp) { if (n <= 1) return n; if (dp[n] != -1) return dp[n]; dp[n] = fib(n - 1, dp) + fib(n - 2, dp); return dp[n]; }

Usage:

int n = 10; vector<int> dp(n + 1, -1); cout << fib(n, dp);

7. How Memoization Works

Suppose:

fib(5)

First time:

fib(5) ↓ fib(4) ↓ fib(3) ↓ ...

Results are stored:

dp[0] = 0 dp[1] = 1 dp[2] = 1 dp[3] = 2 dp[4] = 3 dp[5] = 5

If later we need:

fib(3)

we don't calculate it again.

We simply do:

if (dp[3] != -1) return dp[3];

8. Bottom-Up DP — Tabulation

Bottom-up works in the opposite direction.

Instead of starting with the final problem, we start with the smallest subproblems.

This is called Tabulation.

For Fibonacci:

F(0) = 0 F(1) = 1 F(2) = F(1) + F(0) F(3) = F(2) + F(1) F(4) = F(3) + F(2) ...

C++:

int fib(int n) { if (n <= 1) return n; vector<int> dp(n + 1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }

9. Memoization vs Tabulation

FeatureMemoizationTabulation
DirectionTop → DownBottom → Up
TechniqueRecursionIteration
Uses call stackYesNo
Stores resultsYesYes
Usually easier to deriveYesSometimes
Risk of recursion depthYesNo
Can avoid unused statesOftenUsually computes planned states

Easy memory trick:

Memoization = Recursion + Cache Tabulation = Table + Loop

10. The Most Important DP Question

When you see a DP problem, don't immediately write code.

First ask:

What does dp[i] mean?

This is called defining the DP state.

For example:

dp[i] = Fibonacci number at position i

or:

dp[i] = minimum cost to reach position i

or:

dp[i] = maximum profit using first i items

A good state definition makes the rest of the solution much easier.

11. Four Main Steps to Solve DP Problems

A very useful process is:

1. Define the state ↓ 2. Find the recurrence/transition ↓ 3. Define base cases ↓ 4. Decide computation order

Let's understand each.

12. Step 1 — Define the State

Suppose:

You can climb either 1 or 2 stairs at a time. How many ways can you reach stair n?

Define:

dp[i] = number of ways to reach stair i

That's our state.

13. Step 2 — Find the Transition

To reach stair i, the previous step could have been:

i - 1

or:

i - 2

Therefore:

dp[i] = dp[i-1] + dp[i-2]

This is the transition or recurrence relation.

14. Step 3 — Base Cases

What happens at the beginning?

dp[0] = 1 dp[1] = 1

Why dp[0] = 1?

There is one way to be at the starting position: do nothing.

Then:

dp[2] = dp[1] + dp[0] = 1 + 1 = 2

The two ways are:

1 + 1 2

15. Step 4 — Compute the Answer

int climbStairs(int n) { vector<int> dp(n + 1); dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }

Complexity:

Time: O(n)
Space: O(n)

16. Space Optimization

Notice something:

dp[i] = dp[i-1] + dp[i-2]

We don't need the entire array.

We only need the previous two values.

So:

int climbStairs(int n) { if (n <= 1) return 1; int prev2 = 1; int prev1 = 1; for (int i = 2; i <= n; i++) { int current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; }

Now:

Time: O(n)
Space: O(1)

This technique is called Space Optimization.

17. The Classic 0/1 Knapsack Problem

One of the most important DP problems is 0/1 Knapsack.

Suppose you have:

Items: Weight Value 2 3 3 4 4 5 5 8

Bag capacity:

5

You want to maximize the total value.

Each item can either be:

Take it OR Don't take it

That's why it's called 0/1.

0 = don't take 1 = take

18. Why Greedy Doesn't Always Work

You learned Greedy before.

For 0/1 Knapsack, simple greedy strategies aren't generally guaranteed to give the optimal answer.

Why?

Because an item with the best value/weight ratio may prevent a better combination.

So we consider choices systematically using DP.

19. Knapsack DP State

Define:

dp[i][w]

as:

Maximum value we can obtain using the first i items with capacity w.

Now we have two choices.

Don't take item

dp[i][w] = dp[i-1][w]

Take item

If its weight fits:

dp[i][w] = value[i-1] + dp[i-1][w-weight[i-1]]

Therefore:

dp[i][w] = max( dp[i-1][w], value[i-1] + dp[i-1][w-weight[i-1]] )

20. 0/1 Knapsack C++ Code

int knapsack( vector<int>& weight, vector<int>& value, int capacity ) { int n = weight.size(); vector<vector<int>> dp( n + 1, vector<int>(capacity + 1, 0) ); for (int i = 1; i <= n; i++) { for (int w = 0; w <= capacity; w++) { // Don't take item dp[i][w] = dp[i - 1][w]; // Take item if possible if (weight[i - 1] <= w) { dp[i][w] = max( dp[i][w], value[i - 1] + dp[i - 1][w - weight[i - 1]] ); } } } return dp[n][capacity]; }

Complexity:

Time = O(n × capacity) Space = O(n × capacity)

21. Another Classic: Coin Change

Suppose coins are:

1, 2, 5

Target:

11

Find the minimum number of coins.

One solution:

5 + 5 + 1

Answer:

3

DP State

Define:

dp[x] = minimum coins required to make amount x

Transition:

dp[x] = min( dp[x - coin] + 1 )

for every coin that can be used.

C++ Code

int coinChange(vector<int>& coins, int amount) { const int INF = amount + 1; vector<int> dp(amount + 1, INF); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (coin <= i) { dp[i] = min( dp[i], dp[i - coin] + 1 ); } } } if (dp[amount] == INF) return -1; return dp[amount]; }

Complexity:

Time = O(amount × number_of_coins) Space = O(amount)

22. 0/1 Knapsack vs Unbounded Knapsack

This is an important distinction.

0/1 Knapsack

Each item can be used once.

Item → Take / Don't Take

Unbounded Knapsack

An item can be used multiple times.

Item → Can take again

Coin Change is generally an example of an unbounded setting because the same coin denomination can be used repeatedly.

23. Longest Common Subsequence (LCS)

Another extremely important DP problem is LCS.

Suppose:

A = "abcde" B = "ace"

The longest common subsequence is:

"ace"

Notice:

a b c d e | | | a c e

The characters don't have to be adjacent.

24. LCS DP State

Define:

dp[i][j]

as:

LCS length between the first i characters of A and the first j characters of B.

Now compare the last characters.

If they match:

A[i-1] == B[j-1]

then:

dp[i][j] = 1 + dp[i-1][j-1]

If they don't match:

dp[i][j] = max( dp[i-1][j], dp[i][j-1] )

25. LCS C++ Code

int lcs(string a, string b) { int n = a.size(); int m = b.size(); vector<vector<int>> dp( n + 1, vector<int>(m + 1, 0) ); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { 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]; }

Complexity:

Time = O(n × m) Space = O(n × m)

26. LCS vs Longest Common Substring

Don't confuse these.

Subsequence

Characters don't need to be continuous.

"abcde" "ace" LCS = "ace"

Substring

Characters must be continuous.

"abcdef" "zcdxy" Common substring = "cd"

This distinction appears frequently in interviews and competitive programming.

27. Fibonacci: A Complete DP Evolution

It's useful to see how a problem evolves.

Version 1 — Normal recursion

int fib(int n) { if (n <= 1) return n; return fib(n-1) + fib(n-2); }

Time:

O(2^n)

Version 2 — Memoization

int fib(int n, vector<int>& dp) { if (n <= 1) return n; if (dp[n] != -1) return dp[n]; return dp[n] = fib(n-1, dp) + fib(n-2, dp); }

Time:

O(n)

Space:

O(n)

Version 3 — Tabulation

int fib(int n) { vector<int> dp(n + 1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }

Time:

O(n)

Space:

O(n)

Version 4 — Space Optimized

int fib(int n) { if (n <= 1) return n; int prev2 = 0; int prev1 = 1; for (int i = 2; i <= n; i++) { int current = prev1 + prev2; prev2 = prev1; prev1 = current; } return prev1; }

Time:

O(n)

Space:

O(1)

This is an excellent example of how DP can transform an inefficient recursive solution into an efficient one.

28. DP State Patterns

Most DP problems can be recognized by their state structure.

1D DP

dp[i]

Examples:

  • Fibonacci
  • Climbing Stairs
  • House Robber
  • Minimum Cost Climbing Stairs

2D DP

dp[i][j]

Examples:

  • LCS
  • Edit Distance
  • 0/1 Knapsack
  • Grid paths

3D DP

dp[i][j][k]

Used when three changing parameters are necessary.

For example:

position remaining capacity number of selected items

29. Common DP Categories

You will encounter many patterns.

1. Linear DP

dp[i]

Examples:

  • Fibonacci
  • Climbing Stairs
  • House Robber

2. Grid DP

dp[i][j]

Examples:

  • Unique Paths
  • Minimum Path Sum

3. Knapsack DP

Examples:

  • 0/1 Knapsack
  • Unbounded Knapsack
  • Subset Sum
  • Partition Equal Subset Sum

4. String DP

Examples:

  • LCS
  • Longest Palindromic Subsequence
  • Edit Distance

5. Interval DP

State represents an interval:

dp[l][r]

Examples:

  • Matrix Chain Multiplication
  • Burst Balloons
  • Palindrome partitioning variants

6. Tree DP

DP is performed on tree nodes.

Examples:

  • Maximum independent set on a tree
  • Tree diameter variants
  • Maximum path problems

7. Bitmask DP

Uses bits to represent states.

Example:

dp[mask][i]

Common in subset/permutation problems.

8. Digit DP

Used for counting numbers satisfying digit-related constraints.

9. DP on DAGs

Use graph structure and topological ordering.

30. DP on a Grid

Consider:

1 2 3 4 5 6 7 8 9

Suppose you start at the top-left and can move:

Right → Down ↓

How many ways can you reach the bottom-right?

Define:

dp[i][j] = number of ways to reach cell (i,j)

To reach (i,j), you can come from:

(i-1,j)

or:

(i,j-1)

Therefore:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

This is a very common DP pattern.

31. House Robber Example

Suppose houses contain:

[2, 7, 9, 3, 1]

You cannot rob two adjacent houses.

You want maximum money.

At every house you have two choices:

Don't rob current house OR Rob current house

Define:

dp[i] = maximum money from first i houses

Transition:

dp[i] = max( dp[i-1], dp[i-2] + money[i] )

Why?

If you rob house i, you cannot rob the previous one.

C++:

int rob(vector<int>& money) { int n = money.size(); if (n == 0) return 0; if (n == 1) return money[0]; vector<int> dp(n); dp[0] = money[0]; dp[1] = max(money[0], money[1]); for (int i = 2; i < n; i++) { dp[i] = max( dp[i - 1], dp[i - 2] + money[i] ); } return dp[n - 1]; }

Complexity:

Time = O(n) Space = O(n)

This can also be optimized to O(1) space.

32. DP and State Transition

A useful way to think about DP is:

STATE ↓ What information describes the current problem? ↓ CHOICES ↓ What decisions can I make? ↓ TRANSITION ↓ How does each choice change the state? ↓ BASE CASE ↓ What happens at the smallest state?

For example, House Robber:

State: dp[i] Choices: Take house Don't take house Transition: max( don't take, take + dp[i-2] ) Base: dp[0], dp[1]

33. How to Recognize a DP Problem

Look for these signals:

Signal 1: "Maximum"

Maximum profit Maximum value Maximum length

Signal 2: "Minimum"

Minimum cost Minimum number of operations Minimum coins

Signal 3: "Number of ways"

How many ways? How many possible paths? How many combinations?

Signal 4: Choices

Take / Don't take Choose A / Choose B Move right / Move down Buy / Sell

Signal 5: Repeated subproblems

If recursion keeps solving the same state again, DP may help.

34. A General DP Template

Memoization

int solve(int state) { if (base_case) return base_value; if (dp[state] != -1) return dp[state]; dp[state] = ...; return dp[state]; }

Tabulation

vector<int> dp(n + 1); initialize base cases; for (int state = smallest; state <= largest; state++) { dp[state] = transition; } return dp[n];

For 2D:

vector<vector<int>> dp( n + 1, vector<int>(m + 1) ); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = transition; } }

35. DP Complexity

A powerful rule:

DP complexity is often approximately: number of states × transitions per state.

Example:

Fibonacci

States:

n

Transitions per state:

constant

Therefore:

O(n)

Knapsack

States:

n × capacity

Transitions:

constant

Therefore:

O(n × capacity)

LCS

States:

n × m

Transitions:

constant

Therefore:

O(n × m)

This way of thinking is very useful in DP.

36. DP vs Backtracking

You studied Backtracking earlier.

Backtracking

Try choice ↓ Explore ↓ Undo ↓ Try another choice

It may explore many possibilities.

DP

Solve state ↓ Store result ↓ Reuse result

The key difference is that DP reuses overlapping subproblems, while backtracking typically explores a decision tree.

Sometimes a backtracking problem can be converted into DP if many different paths reach the same state.

37. DP vs Greedy

Greedy

Makes the best local decision:

Best now ↓ Commit ↓ Continue

DP

Considers possible choices and stores the best result for each state:

Choice A ──┐ ├── Best result Choice B ──┘

Greedy is generally faster/simpler when it is provably correct.

DP is useful when local choices aren't sufficient and subproblem reuse exists.

38. DP vs Divide and Conquer

The easiest comparison:

Divide & Conquer ↓ Independent subproblems ↓ Solve separately ↓ Combine
Dynamic Programming ↓ Overlapping subproblems ↓ Solve once ↓ Store ↓ Reuse

39. Common DP Problems You Should Know

For interviews and DSA practice, these are especially important:

Beginner

  1. Fibonacci
  2. Climbing Stairs
  3. Min Cost Climbing Stairs
  4. House Robber
  5. Maximum Subarray

Intermediate

  1. Coin Change
  2. 0/1 Knapsack
  3. Subset Sum
  4. Partition Equal Subset Sum
  5. Unique Paths
  6. Minimum Path Sum
  7. Longest Increasing Subsequence
  8. Longest Common Subsequence

Advanced

  1. Edit Distance
  2. Matrix Chain Multiplication
  3. Longest Palindromic Subsequence
  4. Interval DP
  5. Tree DP
  6. Bitmask DP
  7. Digit DP
  8. DP on DAGs

40. The Most Important DP Skill

Don't memorize 20 different formulas.

Instead, learn to derive them.

When you see a problem, ask:

1. What is my state? ↓ 2. What choices do I have? ↓ 3. What happens after each choice? ↓ 4. Can I express the answer using smaller states? ↓ 5. What are the base cases? ↓ 6. How many states exist? ↓ 7. How many transitions per state?

This is the real skill behind DP.

41. A Practical DP Example

Suppose:

You have stairs n. You can climb either 1 or 2 steps. Find the number of ways to reach the top.

Step 1 — State

dp[i] = number of ways to reach stair i

Step 2 — Choices

1 step 2 steps

Step 3 — Transition

dp[i] = dp[i-1] + dp[i-2]

Step 4 — Base cases

dp[0] = 1 dp[1] = 1

Step 5 — Complexity

States:

n

Work per state:

O(1)

Therefore:

Time = O(n) Space = O(n)

Step 6 — Optimize

Only previous two states are required:

Space = O(1)

This six-step process is exactly how you should approach many DP problems.

42. DP Mental Model

Keep this picture in your mind:

BIG PROBLEM │ ↓ Smaller States / | \ / | \ State A State B State C │ │ │ └───────┼───────┘ ↓ Store Answers ↓ Reuse Answers ↓ FINAL ANSWER

Or even simpler:

DP Problem ↓ Break into states ↓ Find recurrence ↓ Solve each state once ↓ Store ↓ Reuse ↓ Answer

Final Summary

Dynamic Programming = solving overlapping subproblems efficiently by storing their results.

The two most important properties are:

1. Overlapping Subproblems 2. Optimal Substructure

The two main approaches are:

Memoization = Top-Down = Recursion + Cache
Tabulation = Bottom-Up = Table + Iteration

The most important DP concepts are:

  • State → What does dp[i] or dp[i][j] represent?
  • Transition → How do we calculate the current state?
  • Base Case → What are the smallest states?
  • Computation Order → In what order should states be calculated?
  • Space Optimization → Do we need the entire DP table?
  • State count × transitions → Often determines complexity.

Important examples

ProblemTypical DP
Fibonaccidp[i]
Climbing Stairsdp[i]
House Robberdp[i]
Coin Changedp[amount]
0/1 Knapsackdp[i][capacity]
LCSdp[i][j]
Grid Pathsdp[i][j]
Edit Distancedp[i][j]
LISdp[i] / optimized variants

The one rule to remember

Don't start by asking "Which DP formula should I memorize?" Start by asking "What is the state, what choices do I have, and how can I derive the current answer from smaller states?"

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy