Computer Science
Grade 11
20 min
Dynamic Programming
Dynamic Programming
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define Dynamic Programming and identify its two key characteristics: optimal substructure and overlapping subproblems.
Differentiate between the top-down (memoization) and bottom-up (tabulation) approaches to solving DP problems.
Formulate a recurrence relation for a given DP problem.
Implement a DP solution for a classic problem like the Fibonacci sequence or Climbing Stairs.
Trace the execution of a DP algorithm using a memoization cache or a tabulation table.
Analyze and explain the time and space complexity improvements of a DP solution over a naive recursive one.
Ever wonder how your GPS finds the shortest route in a massive city almost instantly? 🗺️ It's not magic; it's a clever problem-solving technique you're about to learn!
This l...
2
Key Concepts & Vocabulary
TermDefinitionExample
Dynamic Programming (DP)An algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.To calculate the 10th Fibonacci number, we first calculate and store the 2nd, 3rd, 4th, etc., and reuse those results instead of re-calculating them from scratch each time.
Optimal SubstructureA property where the optimal solution to a problem can be constructed from the optimal solutions of its subproblems.The shortest path from your home to school through the library is the sum of the shortest path from home to the library and the shortest path from the library to school.
Overlapping SubproblemsA property where a r...
3
Core Syntax & Patterns
The DP Recurrence Relation
DP[state] = function(DP[previous_states])
This is the core formula of any DP solution. It defines how to solve a larger problem (the current state) by using the solutions to smaller, already-solved subproblems (the previous states). Identifying this relation is the most crucial step.
Memoization Pattern (Top-Down)
function solve(state):
if state in memo: return memo[state]
if is_base_case(state): return base_value
result = solve(subproblem1) + solve(subproblem2)
memo[state] = result
return result
Use this pattern for a natural recursive solution. The function calls itself to solve smaller problems, but it uses a 'memo' (cache) to avoid re-computing any subproblem it has seen before.
Tabulation Pattern (Bottom-Up)
dp_table...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
Suppose the 'Climbing Stairs' problem is modified so you can now take 1, 2, or 3 steps at a time. What would be the new recurrence relation for `ways(n)`?
A.ways(n) = ways(n-1) + ways(n-2) + ways(n-3)
B.ways(n) = ways(n-1) + 2 * ways(n-2) + 3 * ways(n-3)
C.ways(n) = ways(n-3)
D.ways(n) = ways(n-1) + 3
Challenging
You are tracing a memoization solution for Climbing Stairs (1 or 2 steps). The function is `climb(n)`. After the initial call `climb(5)` is made, and the calls `climb(4)` and `climb(3)` have just completed and returned, what key-value pairs MUST be in the `memo` cache?
A.{5: 8, 4: 5, 3: 3}
B.{0: 1, 1: 1, 2: 2}
C.{5: 8}
D.{0: 1, 1: 1, 2: 2, 3: 3, 4: 5}
Challenging
A student writes the following tabulation code for Fibonacci: `dp = new Array(n+1); dp[0]=0; for i from 1 to n: dp[i] = dp[i-1] + dp[i-2]; return dp[n];`. What is the primary error in this code?
A.The array size should be `n`, not `n+1`.
B.The base case for `dp[1]` is not set, leading to incorrect calculations.
C.The loop should start from 2, not 1.
D.The recurrence relation `dp[i-1] + dp[i-2]` is incorrect.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free