Skip to main content
Code ScholarsCodeScholars

Advanced Algorithm Design · Algorithm Design

Dynamic Programming

Dynamic programming solves overlapping subproblems by storing results and building answers from smaller states.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

Students learn to name the state first; code comes after the recurrence is clear.

Guided Lesson Notes

Understanding Dynamic Programming

Dynamic Programming focuses on overlapping subproblems, reusable answers, and turning recursion into a table or memo. Dynamic programming solves overlapping subproblems by storing results and building answers from smaller states.

Model: define one state as a smaller question whose answer can help build larger answers.

Invariant: when a state is used, every smaller state it depends on must already be correct or memoized.

Implementation: state definitions, recurrence formulas, base cases, table order, memoization maps, and reconstruction when needed.

Use Dynamic Programming when the problem asks for best, count, longest, shortest, ways, or choices over prefixes, positions, capacities, or subsets.

Visual Model

A small picture for Dynamic Programming

0123012301230123012301230

Key Ideas

  • State definition
  • Recurrence relation
  • Memoization and tabulation

Practice Prompts

  • Turn recursive Fibonacci into memoized Fibonacci.
  • Define states for a coin-change or grid-path problem.

Vocabulary

Terms students should be able to say clearly

State

A smaller subproblem described by indexes, capacity, mask, or other parameters.

Recurrence

The formula that builds one state from smaller states.

Base case

A state whose answer is known immediately.

Memoization

Top-down caching of recursive answers.

Tabulation

Bottom-up filling of a table.

Transition

One possible move from previous states into the current state.

Worked Example

Worked example: tracing Dynamic Programming

Trace a small input, focusing on state definition.

  1. 1Write a small input where Dynamic Programming is clearly useful.
  2. 2Label the part of the input related to State definition.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Trace a small inputSmall nUse a tiny example to understand state changes before coding.
Implement the core ideaDepends on topicChoose data structures that match the operations you need.
Analyze growthBig-OExplain how work changes as the input gets larger.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Dynamic Programming interview problem: Edit Distance

Interview hard

Problem

Given two strings, compute the minimum number of insertions, deletions, and replacements needed to convert the first string into the second.

Input

The first line contains word1. The second line contains word2.

Output

Print the minimum edit distance.

Sample Input

horse
ros

Sample Output

3

Why the sample works

One optimal path is horse -> rorse -> rose -> ros.

Approach

  1. 1Let dp[i][j] be the edit distance between the first i characters of word1 and the first j characters of word2.
  2. 2Base cases convert a prefix to an empty string using deletions or insertions.
  3. 3Matching characters copy dp[i - 1][j - 1].
  4. 4Different characters take one plus the best insert, delete, or replace move.

O(nm) time and O(nm) extra space.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String a = sc.nextLine().trim();
    String b = sc.nextLine().trim();

    int n = a.length();
    int m = b.length();
    int[][] dp = new int[n + 1][m + 1];

    for (int i = 0; i <= n; i++) dp[i][0] = i;
    for (int j = 0; j <= m; j++) dp[0][j] = j;

    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
          dp[i][j] = dp[i - 1][j - 1];
        } else {
          dp[i][j] = 1 + Math.min(
            dp[i - 1][j - 1],
            Math.min(dp[i - 1][j], dp[i][j - 1])
          );
        }
      }
    }

    System.out.println(dp[n][m]);
  }
}

Python Solution

a = input().strip()
b = input().strip()

n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]

for i in range(n + 1):
    dp[i][0] = i
for j in range(m + 1):
    dp[0][j] = j

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i - 1] == b[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = 1 + min(
                dp[i - 1][j - 1],
                dp[i - 1][j],
                dp[i][j - 1],
            )

print(dp[n][m])

Practice Challenge

Make the idea your own

Create a two-minute explanation of Dynamic Programming: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler