Dynamic Programming Patterns — 1D, 2D, Knapsack, Subsequences

Design DP states and transitions for sequences, grids, capacities, and subsequences.

Est. 120 min Updated Suggest a fix
💡 Note
Prerequisites: recursion, arrays, loops, and the Dynamic Programming lesson (Lesson 20). That earlier lesson introduces memoization and tabulation; here we practise state design across reusable problem families.

Objectives: make a problem smaller without losing information

Dynamic programming applies when a problem has overlapping subproblems and an optimal substructure: smaller answers can be reused to build the full answer. For each task, write down the state, recurrence, base cases, evaluation order, and answer location before writing code. A state is a compact description of everything from the past that can affect the future—not a copy of the full history.

🎯 Pro Tip
To practise interview framing and dry runs, go to Interview Problem-Solving Patterns →. This lesson focuses on DP derivation and implementation, not duplicate interview questions.

1. Start with a state and recurrence

Ask: what does one subproblem mean? What choices are available next? If two paths reach the same state, can their remaining work be solved identically? For a “minimum cost” problem, the recurrence often takes a minimum over predecessor states; for “count ways,” it sums counts. Do not mix these objectives: the same state space can have a different recurrence depending on whether the question asks for a count, optimum, or feasibility.

PatternState exampleTransition ideaTypical table
1D sequencedp[i] = best answer through index iUse a small set of earlier statesOne array
2D grid / two prefixesdp[r][c] = answer upon reaching cellCombine legal cells immediately beforeRows × columns
0/1 knapsackdp[c] = best value under capacity cSkip item or take it onceCapacity array or items × capacity
Subsequencedp[i] = best subsequence ending at iExtend compatible earlier endpointsOften O(n²); optimisations exist

2. 1D DP: decisions along a sequence

In the staircase example, each step can be reached from one or two steps below. Let ways[i] count ways to reach step i; then ways[i] = ways[i−1] + ways[i−2]. Define the starting values consistently with the problem: there is one way to stand at step zero (take no moves), which makes the recurrence clean. This is also a model for “take one of a small number of previous states.”

Count one- or two-step climbs · C
#include <stddef.h>
#include <stdint.h>

uint64_t count_climbs(int n) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    uint64_t two_back = 1;
    uint64_t one_back = 1;
    for (int step = 2; step <= n; step++) {
        uint64_t current = one_back + two_back;
        two_back = one_back;
        one_back = current;
    }
    return one_back;
}

Only two preceding states are needed, so the recurrence can be compressed from O(n) storage to O(1). The return type is finite: sufficiently large results overflow uint64_t. If the task asks for counts at large n, use a stated modulus or a big-integer representation rather than assuming arithmetic is unbounded.

3. 2D DP: move through a grid

Let ways[r][c] count paths to a cell when moves are only right or down and all cells are open. Every non-start cell can be entered from above or left. A blocked cell has zero ways. To count paths with obstacles, initialize the first row and column through the same transition; a blocked cell resets the path count to zero, which prevents paths from passing through it.

Grid paths with blocked cells · C
#include <stdint.h>
#define MAX_SIDE 100

uint64_t count_grid_paths(int rows, int cols, int blocked[MAX_SIDE][MAX_SIDE]) {
    if (rows <= 0 || cols <= 0 || rows > MAX_SIDE || cols > MAX_SIDE) return 0;
    uint64_t ways[MAX_SIDE][MAX_SIDE] = {{0}};
    if (blocked[0][0]) return 0;
    ways[0][0] = 1;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (blocked[r][c]) {
                ways[r][c] = 0;
                continue;
            }
            if (r > 0) ways[r][c] += ways[r - 1][c];
            if (c > 0) ways[r][c] += ways[r][c - 1];
        }
    }
    return ways[rows - 1][cols - 1];
}

The function checks dimensions against its fixed storage. For a large grid, the table can be reduced to one row because each cell needs only the value above and the value to its left. Count overflow still needs a defined policy. The state interpretation is “number of paths ending at this cell,” not “number of paths from this cell onward”; both are possible, but their traversal direction and base cases differ.

4. 0/1 Knapsack: each item is chosen at most once

Given weights and values, choose items within a capacity to maximise total value. For each item and capacity, either skip it or take it once if it fits. A one-dimensional optimization updates capacities in descending order. Descending order is crucial: it ensures the current item cannot be reused during the same iteration. An ascending loop instead describes the unbounded variant where repeated copies are allowed.

0/1 knapsack with one-dimensional storage · C
#include <stddef.h>

int knapsack_01(const int weight[], const int value[], int count, int capacity) {
    if (capacity < 0 || count < 0) return 0;
    int best[capacity + 1];
    for (int c = 0; c <= capacity; c++) best[c] = 0;
    for (int item = 0; item < count; item++) {
        for (int c = capacity; c >= weight[item]; c--) {
            int take = best[c - weight[item]] + value[item];
            if (take > best[c]) best[c] = take;
        }
    }
    return best[capacity];
}

This C99 variable-length array should be replaced by checked dynamic allocation when capacity is large or untrusted; the teaching version makes the state visible. If all values are non-negative and the capacity is a limit, initializing to zero correctly allows choosing no items. To reconstruct chosen items, store decisions or retain the full DP table and trace backward; the compressed array alone does not preserve every decision.

5. Subsequences: order matters, adjacency does not

A subsequence keeps relative order but may skip elements. For the longest increasing subsequence (LIS), define length[i] as the length of the longest increasing subsequence ending exactly at i. Try each earlier j whose value is smaller, then extend its best ending sequence. This direct recurrence is O(n²), simple to reason about and often the right baseline before an O(n log n) optimisation is introduced.

Longest increasing subsequence length, O(n²) · C
#include <stddef.h>

int lis_length(const int values[], int n) {
    if (n <= 0) return 0;
    int length[n];
    int answer = 1;
    for (int i = 0; i < n; i++) {
        length[i] = 1;
        for (int j = 0; j < i; j++) {
            if (values[j] < values[i] && length[j] + 1 > length[i])
                length[i] = length[j] + 1;
        }
        if (length[i] > answer) answer = length[i];
    }
    return answer;
}

The strict comparison means equal values cannot extend one another; replace it with ≤ for a longest non-decreasing subsequence. To recover an actual subsequence, keep a predecessor index whenever the best value improves, remember the endpoint of the global best, and follow predecessors backward. Be precise about whether the problem requests the length, one sequence, or the number of optimal sequences.

6. Choose table order and space carefully

Tabulation is valid only when dependencies are already computed. In grid DP, row-major order works because each state depends on the previous row and the current row’s previous column. In 0/1 knapsack, descending capacity preserves the previous item layer. If an optimized update order feels mysterious, first write the full two-dimensional table; compress space only after the dependency direction is clear.

📌 Real World Example
For an order-counting task, two different histories that reach the same state may be merged only if their future choices and contribution are identical. If the future depends on the last colour, remaining coupon, or previous item, include that information in the state instead of accidentally merging unlike histories.

7. Common mistakes

  • Writing code before defining the state: informal state meanings cause wrong transitions. Write one sentence defining what every cell stores.
  • Missing base cases: a recurrence does not define the first state automatically. Test the smallest valid input by hand.
  • Wrong knapsack loop direction: ascending capacity lets one item feed its own later states; descending capacity enforces 0/1 use.
  • Claiming an optimised space table can reconstruct a solution: compressed values may discard decisions. Keep predecessor/choice data when reconstruction is required.

8. Practice

  1. Count ways to climb n stairs using 1, 2, or 3 steps. Define base cases before deriving the recurrence.
  2. Find the minimum cost to travel from top-left to bottom-right in a grid, moving only right/down. State how obstacles change the recurrence.
  3. Modify 0/1 knapsack to return both the best value and a chosen-item list. Explain the extra memory needed.
  4. Change the LIS solution to allow equal adjacent subsequence values, then add predecessor reconstruction.
  5. For each exercise, label the state, transition, base case, traversal order, answer cell, time, and space complexity.

🎯 Key Takeaways

  • ✓A DP state must preserve exactly the information future decisions need.
  • ✓Write the recurrence and base cases before choosing memoization or tabulation.
  • ✓1D, grid, knapsack, and subsequence problems are common state-space shapes.
  • ✓Descending capacity in 0/1 knapsack prevents reusing the current item.
  • ✓Space compression depends on dependency order and can lose reconstruction information.
  • ✓The Interview Problem-Solving Patterns unit offers separate interview drills for applying these ideas.

Next

Use index movement and maintained range state for another family of linear-time techniques.

Lesson 25 · Two Pointers and Sliding Window →

HELP US IMPROVE

How was this lesson?

Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.

Choose your feedback

Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.

Share

Discussion

0

Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.

Continue with GitHub
Loading...