codejeet
|tips

Dynamic Programming for Beginners: From Recursion to Tabulation

Break down dynamic programming step by step — identify subproblems, build recurrence relations, and convert recursion to efficient DP solutions.

Dynamic programming intimidates more interview candidates than any other topic. But DP is a learnable skill, not a talent. Once you understand the underlying process, you can apply it systematically to new problems.

What Dynamic Programming Actually Is

DP is an optimization technique for problems with two properties: overlapping subproblems (the same smaller problem gets solved multiple times) and optimal substructure (the solution to the larger problem can be built from solutions to smaller ones).

If you have written a recursive Fibonacci function and noticed it recalculates the same values repeatedly, you have already encountered the core issue DP solves. Let's illustrate this with the classic Fibonacci example.

# Naive Recursive Fibonacci (Exponential Time)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

# DP with Memoization (Top-Down) - Linear Time
def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# DP with Tabulation (Bottom-Up) - Linear Time
def fib_tab(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]

# Space-Optimized Tabulation
def fib_opt(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

The Four-Step Process

Step 1: Define the State

The state is what you need to know at each subproblem to make a decision. For Climbing Stairs, it is the current step number. For Knapsack, it is the item index and remaining capacity. Ask: "What variables change as I make choices?" Those variables define your state.

Practical Tip: Start by identifying the changing parameters in your recursive solution. If you're solving a problem on a grid, the state might be (row, col). For sequence problems, it's often just the current index i. For problems involving decisions with constraints (like capacity), you'll need additional dimensions.

Step 2: Write the Recurrence Relation

The formula relating a state to smaller states. For Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]. For 0/1 Knapsack: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]). The recurrence captures the decision at each step.

Let's see the recurrence relation for the classic 0/1 Knapsack problem:

def knapsack_01(weights, values, capacity):
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Option 1: Don't take item i-1
            dp[i][w] = dp[i-1][w]
            # Option 2: Take item i-1 if it fits
            if w >= weights[i-1]:
                dp[i][w] = max(dp[i][w],
                              dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][capacity]

Step 3: Identify the Base Cases

The smallest subproblems you can solve directly. For Climbing Stairs: dp[0] = 1, dp[1] = 1. Missing or incorrect base cases are one of the most common DP bugs -- always verify them with small examples.

Practical Tip: Think about the smallest possible input. For many DP problems:

  • When there are no items (i=0), the value is 0
  • When capacity is 0 (w=0), the value is 0
  • When the string is empty, LCS length is 0
  • When you're at the starting position in a grid, there's exactly 1 way to be there

Step 4: Determine the Computation Order

For top-down (memoization), recursion handles this. For bottom-up (tabulation), fill the table so every state you depend on has already been computed -- usually from smaller states to larger ones.

Key Insight: The computation order must respect dependencies. If dp[i] depends on dp[i-1] and dp[i-2], compute from left to right. If dp[i][j] depends on dp[i-1][j] and dp[i][j-1], compute row by row, left to right.

Top-Down vs Bottom-Up

Top-down (memoization) recurses into subproblems and caches results. Easier to write, but has recursion overhead and potential stack overflow.

Bottom-up (tabulation) fills a table iteratively from the base cases. Avoids recursion entirely and often allows space optimization (keeping only the previous row). For interviews, start with top-down, then convert to bottom-up if time allows.

Let's compare both approaches for the Climbing Stairs problem:

# Top-Down (Memoization)
def climb_stairs_memo(n, memo={}):
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = climb_stairs_memo(n-1, memo) + climb_stairs_memo(n-2, memo)
    return memo[n]

# Bottom-Up (Tabulation)
def climb_stairs_tab(n):
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# Space-Optimized Bottom-Up
def climb_stairs_opt(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    return prev1

Common DP Categories

Linear DP. One-dimensional state. Climbing Stairs, House Robber, Maximum Subarray.

Knapsack Variants. Two-dimensional state (item index and capacity). Partition Equal Subset Sum, Target Sum, and Coin Change are all Knapsack in disguise.

LCS Family. Two strings, 2D state. Longest Common Subsequence, Edit Distance, Longest Common Substring.

Grid DP. Two-dimensional grid, move right or down. Unique Paths, Minimum Path Sum.

Interval DP. State defined by a range [i, j]. Burst Balloons, Palindrome Partitioning II.

Let's examine implementations for some key categories:

1. Linear DP: House Robber

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # dp[i] = max money robbing houses up to i
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        # Either rob current house + dp[i-2] or skip it (dp[i-1])
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]

# Space-optimized version
def rob_opt(nums):
    if not nums:
        return 0
    prev2, prev1 = 0, 0
    for num in nums:
        curr = max(prev1, prev2 + num)
        prev2, prev1 = prev1, curr
    return prev1

2. String DP: Longest Common Subsequence

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    # dp[i][j] = LCS length for text1[:i] and text2[:j]
    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]

# Space-optimized version (only need previous row)
def longestCommonSubsequenceOpt(text1, text2):
    if len(text1) < len(text2):
        text1, text2 = text2, text1  # Ensure text2 is shorter

    m, n = len(text1), len(text2)
    prev = [0] * (n + 1)

    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev = curr

    return prev[n]

3. Grid DP: Minimum Path Sum

def minPathSum(grid):
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    # dp[i][j] = min path sum to reach (i, j)
    dp = [[0] * n for _ in range(m)]

    # Initialize first row and column
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # Fill the rest of the table
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[m-1][n-1]

# Space-optimized version (only need previous row)
def minPathSumOpt(grid):
    if not grid or not grid[0]:
        return 0

    m, n = len(grid), len(grid[0])
    dp = [0] * n

    # Initialize first row
    dp[0] = grid[0][0]
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]

    # Process remaining rows
    for i in range(1, m):
        dp[0] += grid[i][0]  # First column
        for j in range(1, n):
            dp[j] = min(dp[j], dp[j-1]) + grid[i][j]

    return dp[n-1]

Practice Progression

Foundation (Linear DP):

  1. Climbing Stairs - Master the basic recurrence relation
  2. House Robber - Learn to handle constraints (can't rob adjacent houses)
  3. Maximum Subarray (Kadane's algorithm) - Understand optimal substructure for subarrays

Knapsack Family: 4. Coin Change - Unbounded knapsack (can use items multiple times) 5. Partition Equal Subset Sum - Subset sum problem (0/1 knapsack variant) 6. Target Sum - Knapsack with a twist (adding +/- signs)

String DP: 7. Longest Common Subsequence - Foundation for all string DP problems 8. Edit Distance - Learn the three operations (insert, delete, replace)

Grid DP: 9. Unique Paths - Basic grid traversal with DP 10. Minimum Path Sum - Grid DP with costs/weights

Advanced: 11. Longest Increasing Subsequence - O(n²) and O(n log n) solutions 12. Burst Balloons - Interval DP with tricky recurrence

Find DP problems tagged by company on the CodeJeet dashboard. DP is especially popular at Amazon, Google, and Microsoft.

Common Mistakes

Incorrect state definition. If your DP table does not capture enough information, add dimensions and optimize later. For example, in the "Best Time to Buy and Sell Stock with Cooldown" problem, you need states for holding stock, not holding stock, and being in cooldown.

Off-by-one errors in base cases. Test with the smallest inputs before coding the full loop. Always check edge cases: empty input, single element, two elements.

Not considering space optimization. Many 2D DP problems only depend on the previous row. Mention this in interviews even if you do not implement it. For example, in knapsack problems, you can reduce space from O(n×W) to O(W).

Forgetting to return the correct value. In bottom-up DP, the answer is usually in dp[n] or dp[m][n], but sometimes it's the maximum/minimum of the entire table.

Not handling initialization properly. For problems where you can start from multiple points (like "Minimum Path Sum" from top-left to bottom-right), initialize the first row and column correctly.

DP is a pattern recognition game. The four-step process gives you a reliable framework for every new problem you encounter. Practice identifying which category a problem belongs to, and you'll quickly recognize the appropriate state definition and recurrence relation. Remember: DP becomes intuitive with practice—each problem you solve makes the next one easier.

Related Articles

Easy Accenture Interview Questions: Strategy Guide

How to tackle 65 easy difficulty questions from Accenture — patterns, time targets, and practice tips.

Hard Accenture Interview Questions: Strategy Guide

How to tackle 11 hard difficulty questions from Accenture — patterns, time targets, and practice tips.

Medium Accenture Interview Questions: Strategy Guide

How to tackle 68 medium difficulty questions from Accenture — patterns, time targets, and practice tips.

Accenture vs Airbnb: Interview Question Comparison

Compare coding interview questions at Accenture and Airbnb — difficulty levels, topic focus, and preparation strategy.