DSA Tutorial #16: Dynamic Programming — From Zero to Hero

Dynamic programming (DP) is the most feared interview topic. But it does not have to be. DP is just recursion with memory — you save the results of subproblems so you do not solve them again. In this article, you will learn the two DP approaches (top-down and bottom-up), how to identify DP problems, and how to solve the most common ones.

We show every example in Kotlin, Python, and Go.

What is Dynamic Programming?

DP solves problems by breaking them into overlapping subproblems and storing the results. Two conditions must be true:

1. Overlapping subproblems: The same subproblem appears multiple times
2. Optimal substructure: The optimal solution can be built from optimal solutions of subproblems

Two Approaches

Top-Down (Memoization)

Write a recursive solution, then add a cache to store results.

Python:

# Fibonacci: top-down with memoization
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

Bottom-Up (Tabulation)

Build a table from the smallest subproblem up to the answer.

Python:

# Fibonacci: bottom-up with tabulation
def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Both approaches have O(n) time and O(n) space. Bottom-up can often be optimized to O(1) space.

Space-optimized Fibonacci:

def fibonacci(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

How to Identify DP Problems

Ask yourself:

1. Can I break this into smaller subproblems?
2. Do subproblems overlap? (Same inputs computed multiple times)
3. Does the problem ask for optimization? (Maximum, minimum, count of ways)

Common DP signals in problem statements:

• “Find the minimum cost to…”
• “Count the number of ways to…”
• “Find the longest/shortest…”
• “Can you reach…?”

Step-by-Step Process

For any DP problem, follow these four steps:

1. Define the state: What does dp[i] represent?
2. Write the recurrence: How does dp[i] relate to previous states?
3. Identify base cases: What are dp[0], dp[1]?
4. Determine the computation order: Bottom-up (small to large) or top-down (large to small)?

1D DP Problems

Climbing Stairs

You can climb 1 or 2 steps at a time. How many ways to reach the top of n stairs?

Python:

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Kotlin:

fun climbStairs(n: Int): Int {
    if (n <= 2) return n
    var prev2 = 1
    var prev1 = 2
    for (i in 3..n) {
        val curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

Go:

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    prev2, prev1 := 1, 2
    for i := 3; i <= n; i++ {
        curr := prev1 + prev2
        prev2 = prev1
        prev1 = curr
    }
    return prev1
}

State: dp[i] = number of ways to reach stair i. Recurrence: dp[i] = dp[i-1] + dp[i-2]. Time: O(n). Space: O(1) optimized.

House Robber

Rob houses along a street. You cannot rob two adjacent houses. Maximize the total amount.

Python:

def rob(nums):
    if len(nums) <= 2:
        return max(nums)
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[-1]

State: dp[i] = max money robbing houses 0..i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Either skip house i (take dp[i-1]) or rob it (take dp[i-2] + nums[i]).

Coin Change

Given coins of different denominations, find the fewest coins to make a target amount.

Python:

def coin_change(coins, amount):
    dp = [float("inf")] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float("inf") else -1

Kotlin:

fun coinChange(coins: IntArray, amount: Int): Int {
    val dp = IntArray(amount + 1) { amount + 1 }
    dp[0] = 0
    for (i in 1..amount) {
        for (coin in coins) {
            if (coin <= i) {
                dp[i] = minOf(dp[i], dp[i - coin] + 1)
            }
        }
    }
    return if (dp[amount] > amount) -1 else dp[amount]
}

Go:

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i && dp[i-coin]+1 < dp[i] {
                dp[i] = dp[i-coin] + 1
            }
        }
    }
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

State: dp[i] = fewest coins for amount i. Recurrence: dp[i] = min(dp[i - coin] + 1) for all coins. Time: O(amount * len(coins)). Space: O(amount).

Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence.

Python:

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

State: dp[i] = length of LIS ending at index i. Time: O(n^2). There is an O(n log n) solution using binary search.

2D DP Problems

Unique Paths

A robot is at the top-left corner of an m x n grid. It can only move right or down. How many unique paths to the bottom-right corner?

Python:

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

Kotlin:

fun uniquePaths(m: Int, n: Int): Int {
    val dp = Array(m) { IntArray(n) { 1 } }
    for (i in 1 until m) {
        for (j in 1 until n) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        }
    }
    return dp[m - 1][n - 1]
}

State: dp[i][j] = number of paths to cell (i, j). Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Time: O(m * n). Space: O(m * n), optimizable to O(n).

Longest Common Subsequence

Given two strings, find the length of their longest common subsequence.

Python:

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Go:

func longestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[m][n]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

State: dp[i][j] = length of LCS of text1[:i] and text2[:j]. Time: O(m * n). Space: O(m * n).

Space Optimization: Rolling Array

You can reduce 2D DP to 1D when each row only depends on the previous row.

Python:

# Unique Paths with O(n) space
def unique_paths_optimized(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    return dp[n - 1]

Common DP Categories

Why DP is Hard (And How to Get Better)

DP is hard because:

1. Defining the state is not obvious. The hardest part is figuring out what dp[i] means.
2. The recurrence requires insight. You need to see how the current problem relates to smaller subproblems.
3. Many variations exist. Each DP category has its own patterns.

How to improve:

1. Start with brute force recursion. Do not try to write DP directly. Write the recursive solution first.
2. Add memoization. If it works but is slow, add a cache. Now you have top-down DP.
3. Convert to bottom-up. Fill a table instead of using recursion.
4. Optimize space. If each state only depends on the previous row/few values, reduce space.

Common Mistakes

1. Jumping to DP without understanding the recursive structure. Always start with brute force recursion.

2. Wrong base cases. Off-by-one errors in base cases cause wrong results for the entire table.

3. Wrong computation order in bottom-up. Make sure you compute smaller subproblems before larger ones.

4. Forgetting to handle impossible states. Initialize dp with infinity (for minimization) or -infinity (for maximization), not 0.

Practice Problems

What’s Next?

Now you understand the foundations of DP. The next article covers Greedy Algorithms — a simpler approach that works when locally optimal choices lead to a globally optimal solution. You will learn when to use greedy instead of DP.

Next: DSA Tutorial #17: Greedy Algorithms

Full series: DSA from Zero to Interview Ready