Dynamic Programming

Dynamic programming requires students to shift from linear problem-solving to strategic planning, where efficiency depends on recognizing patterns in overlapping steps. Active learning lets them experience the 'aha' moment when repeated work is eliminated, building intuition that static examples cannot provide.

• Grade 12
• Computer Science
• 4 activities
• 30 min–50 min

Learning Objectives

1. Compare the time and space complexity of recursive solutions versus dynamic programming solutions for a given problem.
2. Explain how memoization and tabulation are used to optimize dynamic programming algorithms.
3. Construct a dynamic programming solution for a classic problem, such as the Fibonacci sequence or the 0/1 knapsack problem.
4. Analyze the optimal substructure and overlapping subproblems properties for a given problem to determine if dynamic programming is applicable.
5. Evaluate the efficiency gains achieved by dynamic programming compared to brute-force or naive recursive approaches.

Flipped Classroom

⏱ 45 min·Pairs

Pair Programming: Fibonacci Showdown

Pairs implement recursive Fibonacci, then add memoization and bottom-up tabulation. They time each version with large inputs and graph results. Discuss which approach scales best.

Prepare & details

Differentiate between dynamic programming and recursion with memoization.

Facilitation Tip: During Pair Programming: Fibonacci Showdown, circulate and ask pairs to explain their cache structure before coding, ensuring they understand how keys map to subproblems.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Flipped Classroom

⏱ 50 min·Small Groups

Small Group Stations: Knapsack Builds

Groups rotate through stations: define items/weights/values, code greedy vs. DP, trace tables, test edge cases. Each station yields a shared solution report.

Prepare & details

Explain how dynamic programming avoids redundant calculations.

Facilitation Tip: In Small Group Stations: Knapsack Builds, provide blank grids for tabulation and have groups swap stations to compare solutions before finalizing their own.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Flipped Classroom

⏱ 30 min·Whole Class

Whole Class Trace: Longest Common Subsequence

Project a table; class calls out values row-by-row while coding live. Vote on decisions, then run code to verify. Extend to student-voted problem variants.

Prepare & details

Construct a dynamic programming solution for a classic problem like the Fibonacci sequence or knapsack problem.

Facilitation Tip: For Whole Class Trace: Longest Common Subsequence, use a document camera to let students physically mark the table as you solve, emphasizing how each cell depends on previous ones.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Flipped Classroom

⏱ 35 min·Individual

Individual Optimization: Coin Change Problem

Students adapt DP template to minimize coins for given amounts. Submit code with test cases and complexity analysis for peer review.

Prepare & details

Differentiate between dynamic programming and recursion with memoization.

Facilitation Tip: For Individual Optimization: Coin Change Problem, require students to submit a runtime comparison table between their recursive and tabulated solutions before moving to extension problems.

Setup: Standard classroom, flexible for group activities during class

Materials: Pre-class content (video/reading with guiding questions), Readiness check or entrance ticket, In-class application activity, Reflection journal

• Understand
• Apply
• Analyze
• Self-Management
• Self-Awareness

Teaching This Topic

Teachers should emphasize the 'why' behind each step, not just the 'how.' Start with concrete examples before introducing formal definitions, and always connect back to the problem's structure. Avoid rushing to the algorithm; let students grapple with inefficiency first. Research shows that when students build their own examples of overlapping subproblems, they internalize optimal substructure more deeply.

What to Expect

Successful learning shows when students can explain why tabulation or memoization is chosen for a given problem, trace a solution step-by-step, and articulate the trade-offs between space and time. They should also recognize when dynamic programming is not the right tool, even for recursive problems.

Watch Out for These Misconceptions

Common Misconception

During Pair Programming: Fibonacci Showdown, watch for students who assume memoization and tabulation produce identical stack traces.

What to Teach Instead

Have students print both the memoized recursive calls and the bottom-up iteration steps side by side, then ask them to identify where recursion stacks grow versus where arrays update in-place.

Common Misconception

During Small Group Stations: Knapsack Builds, watch for students who apply dynamic programming to any subset problem without checking for overlapping subproblems.

What to Teach Instead

Provide a non-overlapping problem variant at one station and have groups attempt to fill the table, then discuss why it fails to produce a valid solution.

Common Misconception

During Individual Optimization: Coin Change Problem, watch for students who believe tabulated solutions always outperform recursive ones regardless of input size.

What to Teach Instead

Guide students to time both approaches for inputs of 10, 100, and 1000 coins, then ask them to explain why small inputs may favor recursion due to table overhead.

Assessment Ideas

Quick Check

After Pair Programming: Fibonacci Showdown, present students with a recursive Fibonacci pseudocode snippet and ask them to highlight two repeated subproblems. Then, have them annotate how the memoized version would store and reuse these results.

Discussion Prompt

During Whole Class Trace: Longest Common Subsequence, pose the question: 'When would you choose memoization over tabulation for this problem, and why?' Listen for answers that mention stack depth constraints or the need to reconstruct the actual subsequence.

Exit Ticket

After Individual Optimization: Coin Change Problem, provide a specific coin set and amount. Ask students to outline the tabulation steps, including the DP table definition, recurrence relation, and a filled example for the first five values.

Extensions & Scaffolding

• Challenge advanced students to implement a space-optimized version of the 0/1 knapsack problem using only two rows of the table.
• Scaffolding for struggling students: Provide partially filled tables for the coin change problem with three rows completed as a guide.
• Deeper exploration: Ask students to research and present a dynamic programming problem from bioinformatics or operations research, explaining its optimal substructure and how the table is constructed.

Key Vocabulary

Dynamic Programming	An algorithmic technique that solves complex problems by breaking them into simpler, overlapping subproblems and storing the solutions to these subproblems to avoid recomputation.
Overlapping Subproblems	A property of problems where the same subproblems are encountered multiple times during the computation of the overall solution, making them suitable for dynamic programming.
Optimal Substructure	A property where the optimal solution to a problem can be constructed from the optimal solutions of its subproblems.
Memoization	A top-down dynamic programming technique where the results of expensive function calls are stored (cached) and returned when the same inputs occur again.
Tabulation	A bottom-up dynamic programming technique where solutions to subproblems are computed iteratively and stored in a table, building up to the final solution.