Advanced Algorithm Design · Algorithm Design

Dynamic Programming

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

Enroll Now Text Us Contact Code Scholars Full 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.

The mental model is this: define one state as a smaller question whose answer can help build larger answers. That picture matters because it tells the student what information is available immediately and what must be searched, stored, or recomputed.

The core invariant is that when a state is used, every smaller state it depends on must already be correct or memoized. If a solution cannot state that rule, the code may still run on a sample input but fail on edge cases.

A strong implementation usually uses state definitions, recurrence formulas, base cases, table order, memoization maps, and reconstruction when needed. The goal is not just to memorize an API; the goal is to know why each operation is allowed and what it costs.

In competitive programming, Dynamic Programming tends to appear when the problem asks for best, count, longest, shortest, ways, or choices over prefixes, positions, capacities, or subsets. Spotting that signal is often the difference between a nested-loop solution and an efficient one.

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

Use a tiny input and focus on state definition. The goal is to see how the topic changes state before scaling it to a full problem.

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

Complexity Check

Costs students should be able to explain

Operation	Typical Cost	Reason
Trace a small input	Small n	Use a tiny example to understand state changes before coding.
Implement the core idea	Depends on topic	Choose data structures that match the operations you need.
Analyze growth	Big-O	Explain 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

Why the sample works

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

Approach

1Let dp[i][j] be the edit distance between the first i characters of word1 and the first j characters of word2.
2Base cases convert a prefix to an empty string using deletions or insertions.
3Matching characters copy dp[i - 1][j - 1].
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

Turn the topic into usable problem-solving skill

Students can use this page before a lesson, after a difficult homework assignment, or while preparing for AP Computer Science A extensions, Advanced Topics in CS, USACO growth, or a college data structures course.

Schedule Free Consultation Text Us Open Online Compiler