Project 12: Dynamic Programming Mastery

Build a suite of classic DP problems with table visualizations.

Quick Reference

Attribute Value
Difficulty Level 4: Expert
Time Estimate 3-4 weeks
Language Python (Alternatives: C++, Java, Go)
Prerequisites Projects 4 and 11, strong recursion skills
Key Topics DP, memoization, tabulation, optimization

1. Learning Objectives

By completing this project, you will:

  1. Recognize when a problem has optimal substructure and overlapping subproblems.
  2. Implement memoization and tabulation approaches.
  3. Solve classic DP problems with space optimization.
  4. Visualize DP tables to explain reasoning.

2. Theoretical Foundation

2.1 Core Concepts

  • Overlapping subproblems: Same subproblem solved multiple times.
  • Optimal substructure: Optimal solution built from optimal subsolutions.
  • Memoization: Cache results in a top-down recursion.
  • Tabulation: Build bottom-up tables.

2.2 Why This Matters

Dynamic programming transforms exponential recursion into polynomial solutions and appears in optimization, planning, and NLP.

2.3 Historical Context / Background

The term “dynamic programming” was coined by Bellman in the 1950s for multi-stage decision problems.

2.4 Common Misconceptions

  • Misconception: DP means using a 2D table. Reality: DP is about reusing subsolutions; tables are just one technique.
  • Misconception: Memoization and tabulation are interchangeable. Reality: They trade stack depth for iterative control.

3. Project Specification

3.1 What You Will Build

A DP toolkit that includes problems like Fibonacci, knapsack, edit distance, LIS, and grid path counting, with visualization of state transitions.

3.2 Functional Requirements

  1. Problem suite: At least five classic DP problems.
  2. Two styles: Provide memoized and tabulated solutions.
  3. Visualization: Print DP tables or state graphs.
  4. Benchmarking: Compare naive vs DP performance.

3.3 Non-Functional Requirements

  • Performance: Show clear speedups over naive recursion.
  • Reliability: Tests for correctness across edge cases.
  • Usability: CLI to select a problem and input.

3.4 Example Usage / Output

$ ./dp-tool --problem edit-distance --a kitten --b sitting
Distance: 3
Table saved to output/edit-distance.txt

3.5 Real World Outcome

You will be able to run a DP problem, view the full DP table, and understand how each cell depends on previous ones.

4. Solution Architecture

4.1 High-Level Design

┌───────────┐     ┌──────────────┐     ┌──────────────┐
│ CLI Input │────▶│ DP Library   │────▶│ Visualizer   │
└───────────┘     └──────┬───────┘     └──────────────┘
                            │
                      ┌─────▼─────┐
                      │ Benchmarks│
                      └───────────┘

4.2 Key Components

Component Responsibility Key Decisions
dp.py Implement DP problems Consistent interface
visualize.py Table rendering Text-based tables
benchmarks.py Compare runtimes Time vs ops

4.3 Data Structures

# Example DP table for edit distance
matrix = [[0] * (m + 1) for _ in range(n + 1)]

4.4 Algorithm Overview

Key Algorithm: 0/1 Knapsack (Tabulation)

  1. Build table of size (n+1) x (W+1).
  2. Each cell chooses max of include/exclude.

Complexity Analysis:

  • Time: O(nW)
  • Space: O(nW) (or O(W) optimized)

5. Implementation Guide

5.1 Development Environment Setup

python3 -m venv .venv
. .venv/bin/activate

5.2 Project Structure

dp-tool/
├── src/
│   ├── dp.py
│   ├── visualize.py
│   ├── benchmarks.py
│   └── cli.py
├── output/
└── tests/

5.3 The Core Question You’re Answering

“How does caching subproblem results turn exponential into polynomial time?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. Overlapping subproblems
  2. Optimal substructure
  3. State transitions

5.5 Questions to Guide Your Design

  1. How will you standardize input/output across problems?
  2. How will you visualize tables without overwhelming output?
  3. Which problems show the biggest DP improvement?

5.6 Thinking Exercise

Write the DP recurrence for edit distance and compute a 3x3 example by hand.

5.7 The Interview Questions They’ll Ask

  1. Explain memoization vs tabulation.
  2. Solve the classic coin change problem.
  3. Show how to optimize space in DP.

5.8 Hints in Layers

Hint 1: Start with Fibonacci It is the simplest DP demonstration.

Hint 2: Add a table printer Start with small examples to avoid huge output.

Hint 3: Use a registry of problems Map problem names to functions for clean CLI.

5.9 Books That Will Help

Topic Book Chapter
DP fundamentals “Algorithms Illuminated (Part 3)” Ch. 16-20
Classic DP “Introduction to Algorithms” Ch. 15
Recognizing DP “Grokking Algorithms” Ch. 9

5.10 Implementation Phases

Phase 1: Foundation (6-7 days)

Goals:

  • Implement memoization and tabulation utilities
  • Add Fibonacci and grid paths

Tasks:

  1. Write memo decorator.
  2. Implement two basic DP problems.

Checkpoint: DP results match naive solutions.

Phase 2: Core Problems (7-10 days)

Goals:

  • Add knapsack, LIS, edit distance
  • Add visualization

Tasks:

  1. Implement DP tables.
  2. Export tables to text files.

Checkpoint: Tables render correctly and answers match.

Phase 3: Optimization and Benchmarks (5-7 days)

Goals:

  • Add space-optimized versions
  • Compare performance

Tasks:

  1. Implement 1D DP for knapsack.
  2. Benchmark naive vs DP.

Checkpoint: Clear performance improvement shown.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
DP style memo, tabulation both Compare approaches
Visualization inline, file output file output Avoid huge CLI output
Benchmarks time, ops time + ops Balanced view

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests DP functions Small known inputs
Integration Tests CLI selection Run all problems
Edge Case Tests Empty inputs zero-size values

6.2 Critical Test Cases

  1. Edit distance between identical strings is 0.
  2. Knapsack with weight limit 0 returns 0.
  3. LIS for sorted input equals length.

6.3 Test Data

strings: "kitten", "sitting"
weights: [2, 3, 4], values: [3, 4, 5], W=5

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong base cases Incorrect results Verify initial row/column
Off-by-one in loops Index errors Draw table first
Table too large Memory issues Use space optimization

7.2 Debugging Strategies

  • Print small DP tables and compare to hand calculations.
  • Log transitions for a single cell.

7.3 Performance Traps

Using recursion without memoization leads to exponential time. Add memo early.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add coin change problem.
  • Add staircase ways problem.

8.2 Intermediate Extensions

  • Add DP for matrix chain multiplication.
  • Add path reconstruction for LIS.

8.3 Advanced Extensions

  • Implement bitmask DP (TSP for small n).
  • Add divide-and-conquer DP optimization.

9. Real-World Connections

9.1 Industry Applications

  • Text similarity (edit distance)
  • Resource optimization (knapsack-like problems)
  • CP-Algorithms: DP problem explanations.
  • LeetCode: DP practice problems.

9.3 Interview Relevance

DP is a major interview topic and often used to test problem-solving depth.

10. Resources

10.1 Essential Reading

  • “Algorithms Illuminated (Part 3)” by Roughgarden - Ch. 16-20
  • “Introduction to Algorithms” - Ch. 15

10.2 Video Resources

  • DP tutorials and table walkthroughs

10.3 Tools and Documentation

  • Visualization tools like matplotlib (optional)

11. Self-Assessment Checklist

11.1 Understanding

  • I can identify overlapping subproblems.
  • I can write a DP recurrence.
  • I can optimize space in a DP table.

11.2 Implementation

  • DP answers match known results.
  • Visualization outputs are correct.

11.3 Growth

  • I can choose DP over greedy when appropriate.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Two DP problems solved
  • Memoization and tabulation shown

Full Completion:

  • Five DP problems
  • Table visualization and benchmarks

Excellence (Going Above and Beyond):

  • Bitmask DP or advanced optimizations
  • Performance report

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.