Part 1: Mastering Dynamic Programming — 5 Steps to Solve It (Longest Increasing Subsequence Using Tabulation / Bottom-Up)

Dynamic Programming (DP) has a reputation for being one of the trickiest topics in algorithms. Many learners struggle not because DP is inherently complex, but because they lack a structured approach to reasoning about problems. In this blog, we’ll break DP down into five simple steps that you can apply to most problems.

To make things concrete, we’ll use the Longest Increasing Subsequence (LIS) problem as our running example.

---

## 🧠 5-Step Framework to Solve DP Problems

---

### 1. Visualize Examples (Think in Terms of a DAG)

Almost all DP problems can be imagined as paths in a Directed Acyclic Graph (DAG). Each state represents a choice, and edges represent transitions to future states.

Let’s take our example array:

arr = [3, 1, 8, 2, 5]

Try to imagine all sequences that can be formed by picking numbers in increasing order.
Visualizing a few example sequences helps greatly:

• Starting at 3 → [3, 8] or [3, 5]
• Starting at 1 → [1, 8], [1, 2, 5]
• Starting at 8 → [8]
• etc.

Each number can go to any number greater than it that appears later in the list — this is your DAG.

---

### 2. Find an Appropriate Subproblem

A good DP solution boils down to defining the right subproblem.

For LIS, a natural subproblem is:

What is the longest increasing subsequence starting at index i?

Or more commonly:

What is the LIS ending at index i?

Let’s define:

dp[i] = length of the longest increasing subsequence ending at index i

---

### 3. Find Relationships Among Subproblems

Now that we have dp[i], how do we compute it?

For each index i, look at all previous indices j < i:

• If arr[j] < arr[i], then we can extend the subsequence ending at j.

This gives:

dp[i] = 1 + max(dp[j]) over all j < i where arr[j] < arr[i]

If no such j exists, then dp[i] = 1 (the element itself).

---

### 4. Generalize the Relationship

Combining everything:

dp[i] = 1 + max(dp[j] for all valid j)
otherwise dp[i] = 1

This is our recurrence relation.

The final LIS answer is:

max(dp[i] for all i)

---

### 5. Implement by Solving Subproblems in Order

We fill the dp array from left to right, ensuring all dp[j] values needed for dp[i] have already been computed.

Here’s a full implementation:

def LIS(arr):
    n = len(arr)
    dp = [1] * n  # Every element is a subsequence of length 1

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Testing it:

arr = [3, 1, 8, 2, 5]
print(LIS(arr))  # Output: 3  (The subsequence is [1, 2, 5])

---

Nice, let’s zoom all the way in on this array and see exactly what’s happening:

arr = [3, 1, 8, 2, 5]

Let's go step-by-step:

0. What does dp[i] mean?

dp[i] = length of the Longest Increasing Subsequence that ends exactly at index i

So for each position i, we assume arr[i] is the last element of the subsequence.

---

Step-by-step for [3, 1, 8, 2, 5]

Indexing:
i = 0 1 2 3 4
arr = [3, 1, 8, 2, 5]

Initial state

dp = [1, 1, 1, 1, 1]

Why all 1’s?
Because every single element alone is a subsequence of length 1.

---

i = 0 → element = 3

For i = 0, the loops don’t run (no j < 0), so:

• dp[0] stays 1 → subsequence [3]

Current:

dp = [1, 1, 1, 1, 1]

---

i = 1 → element = 1

We look at all j < 1 → only j = 0.

• j = 0 → compare arr[0] < arr[1] → 3 < 1? ❌ No.

So there is no previous smaller element that can come before 1 in an increasing subsequence.

• dp[1] stays 1 → subsequence [1]

Current:

dp = [1, 1, 1, 1, 1]

Subproblems so far:

• LIS ending at index 0 is 1 ([3])
• LIS ending at index 1 is 1 ([1])

---

i = 2 → element = 8

We look at all j < 2 → j = 0, 1.

j = 0:

• arr[0] < arr[2] → 3 < 8 ✅ We can extend the subsequence ending at index 0.

Candidate length if we extend:
dp[0] + 1 = 1 + 1 = 2

Update:

dp[2] = max(dp[2], dp[0] + 1) = max(1, 2) = 2

j = 1:

• arr[1] < arr[2] → 1 < 8 ✅ We can also extend the subsequence ending at index 1.

Candidate length:
dp[1] + 1 = 1 + 1 = 2

Update:

dp[2] = max(2, 2) = 2

So the best we can do for subsequences ending at 8 is length 2:
Either [3, 8] or [1, 8].

Current:

dp = [1, 1, 2, 1, 1]

---

i = 3 → element = 2

We look at all j < 3 → j = 0, 1, 2.

j = 0:

• arr[0] < arr[3] → 3 < 2? ❌ No. Can't put 2 after 3 in an increasing sequence.

j = 1:

• arr[1] < arr[3] → 1 < 2 ✅ We can extend the subsequence ending at 1.

Candidate length:
dp[1] + 1 = 1 + 1 = 2

Update:

dp[3] = max(dp[3], dp[1] + 1) = max(1, 2) = 2

This corresponds to subsequence [1, 2].

j = 2:

• arr[2] < arr[3] → 8 < 2? ❌ No.

So best subsequence ending at 2 has length 2 → [1, 2].

Current:

dp = [1, 1, 2, 2, 1]

---

i = 4 → element = 5

We look at all j < 4 → j = 0, 1, 2, 3.

j = 0:

• arr[0] < arr[4] → 3 < 5 ✅ Extend subsequence ending at index 0 (which is [3]).

Candidate length:
dp[0] + 1 = 1 + 1 = 2

dp[4] = max(1, 2) = 2

So, one candidate subsequence is [3, 5].

j = 1:

• arr[1] < arr[4] → 1 < 5 ✅ Extend subsequence ending at index 1 ([1]).

Candidate:
dp[1] + 1 = 1 + 1 = 2

dp[4] = max(2, 2) = 2   # no change

So [1, 5] is another subsequence of length 2.

j = 2:

• arr[2] < arr[4] → 8 < 5? ❌ No.

We cannot put 5 after 8.

j = 3:

• arr[3] < arr[4] → 2 < 5 ✅ Extend subsequence ending at index 3 (which was [1, 2]).

Candidate:
dp[3] + 1 = 2 + 1 = 3

dp[4] = max(2, 3) = 3

Now we’ve found a better subsequence ending at 5:
[1, 2, 5] of length 3.

Final dp array:

dp = [1, 1, 2, 2, 3]

---

Final Answer

The LIS length is:

max(dp) = 3

And one actual longest increasing subsequence is:

[1, 2, 5]

(There’s no longer one in this example.)

---

How this is DP (subproblem view)

Each dp[i] depends on smaller indices:

• To compute dp[4] (LIS ending at 5), we reused solutions to earlier subproblems: dp[0], dp[1], dp[2], dp[3].

So the subproblem is:

“What’s the length of the longest increasing subsequence that ends at index i?”

You solve that for i = 0, 1, 2, 3, 4 in order → bottom-up tabulation DP.

---

## 💡 Final Thoughts

Dynamic Programming becomes much easier when you approach it systematically.
By following these 5 steps:

1. Visualize examples
2. Identify subproblems
3. Find relationships
4. Generalize
5. Implement in order

—you can confidently tackle even the most intimidating DP problems.