Turn a huge search into small states by recording what the past can no longer change.
ThinkCompareExplain
Today’s route
A question becomes an explanation.
Try
Enter through a problem. A partial attempt counts.
Connect
Use state, transition, memoization to name what you notice.
Convince
Build an argument a partner can check.
The goal is a method someone else can use.
The opener
Start with a question.
Opening problem
A robot moves from (0,0) to (4,3), only right or up. How many paths avoid the blocked point (2,1)?
Think · 2 min
Sketch, test a small case, or make a first guess.
Pair · 3 min
Compare methods. Find one thing you agree on and one question.
Be ready to share your route, even if it is unfinished.
Compare before checking
Put two attempts in conversation.
Explain
Tell a partner how you started. Let them finish before responding.
Question
Which step feels certain? Which step still needs evidence?
Build
Combine one useful idea from each attempt into a new route.
Can you explain your partner’s method in your own words?
Board conversation
Notice before naming.
Look for structure
01Every path reaches a point from the left or from below.
02Once a path reaches a state, its earlier route matters only through the count already stored there.
03A blocked state contributes zero, so the same local rule handles obstacles cleanly.
Make a conjecture
We think ___ because ___. A case that might break this is ___.
What changed? What stayed the same?
Useful language
Now the language has a job.
state
the information needed to describe the remaining work
transition
the rule that moves from smaller states to a new one
memoization
saving a solved state instead of recomputing it
Use one of these words to explain something you already noticed.
The core idea
Keep the idea. Explain the conditions.
D(i,j)=D(i−1,j)+D(i,j−1)
The idea
Turn a huge search into small states by recording what the past can no longer change.
What to remember
A good state is a small summary that preserves every future-relevant choice.
What information does this method keep?
Worked example
One route, one decision at a time
The problem
On a grid, move right or up from (0,0) to (3,2), but do not visit (1,1). How many paths exist?
Predict each next step
01Write 1 at (0,0); each open cell receives the sum from its left and lower neighbors.
02The unrestricted total is (25) = 10.
03Paths through (1,1) are (12) * (13) = 2 * 3 = 6.
04Subtract: 10 - 6 = 4. The table and the combinatorial subtraction agree.
Which step needs a reason, not just a calculation?
See the structure
A state remembers only what still matters
D(i,j)=D(i−1,j)+D(i,j−1)
For right/up paths, seed D(0,0)=1, assign blocked cells zero, and treat cells outside the grid as zero.
Read the representation
At a grid cell, the next count depends on the neighboring counts, not on the full history of every path. That is the compression that makes dynamic programming possible.
Look together
Point to the part that explains the relationship. Change one input and predict what changes.
What can you see here that was harder to see in words?
Two approaches
Compare the reasoning.
Dynamic programming
01Define a state with enough information for the future.
02Solve smaller states once and reuse them.
03Prove the transition covers every final possibility.
Brute-force search
01Rebuilds the same partial paths repeatedly.
02Can grow exponentially with the number of moves.
03May be correct but wasteful when subproblems overlap.
Which route can you justify? What would you test first?
Reasoning clinic
Find the step that needs repair.
Investigate these concerns
01Rebuilds the same partial paths repeatedly.
02Can grow exponentially with the number of moves.
03May be correct but wasteful when subproblems overlap.
Repair together
Name the missing condition. Try a small counterexample. Rewrite one step so it is justified.
A useful correction explains why the original step fails.
Work together
Fill a state table
Your shared task
Start with a tiny grid. Put 1 at the origin, 0 on blocked cells, and write the transition in words before filling the table.
Explore
4 min - fill a 3 by 3 grid
Compare
6 min - add one blocked cell
Defend
5 min - explain why order does not matter
Everyone should be able to explain the group’s final claim.
Share → connect
What did the room discover?
Bring your evidence
Share a conjecture, a useful example, or a route that changed.
Connections to investigate
01The state is a promise about what the future needs, not a transcript of the past.
02Obstacles and boundary conditions belong in the base cases.
03A counting recurrence becomes an algorithm when the states are stored and visited systematically.
Which observation explains the mechanism?
Try → explain → check
Your turn to build the route
The problem
A staircase has 8 steps. You may climb 1 or 2 steps at a time, but never take two 2-step jumps in a row. How many sequences reach step 8?
Predict each next step
01Let An end with a 1-step jump and Bn end with a 2-step jump.
02Any sequence ending in 1 comes from either state at n - 1: An = A_(n-1) + B_(n-1).
03A sequence ending in 2 must have ended with 1 before it: Bn = A_(n-2).
04Use A0=1 for the empty start, B0=B1=0, and A1=1. The totals for n=0,...,8 are 1,1,2,3,4,6,9,13,19. Answer: 19.
Which step needs a reason, not just a calculation?
Convince a skeptic
Turn a pattern into a proof.
The claim
Dynamic programming is proof by organized reuse.
Build the argument
01Choose a state that contains every fact the future can use.
02Partition solutions by their final move or final decision.
03Show each part maps to exactly one smaller state, then store base cases and apply the transition to the target.
What does each step rely on? Where are the conditions used?
Stretch together
Take the idea somewhere new.
Transfer challenge
A robot moves right or up from (0,0) to (5,4). It may not visit (2,2) or (3,1). How many paths avoid both blocked points?
Choose a route
Name the objects, the conditions, and a relationship that might help. Start with one test case.
What transfers from the earlier example? What is different?
Peer review
Check the argument together.
Restate
Explain the other person’s route before evaluating it.
Test
Try a small case or boundary case. Does every step still make sense?
Revise
Fix an assumption, add a reason, or find a second method.
Where did your thinking change?
Beyond this problem
Where might this idea help?
A connection
Route planning, text alignment, game search, scheduling, and machine-learning sequence models all use the same question: which details of the past can be discarded without changing the best or total future possibilities?
Discuss the model
01What objects or quantities are represented?
02Which relationship from today is preserved?
03What assumption would you check before trusting it?
Invent one more situation with the same structure.
Exit ticket
Leave with an explanation.
Question 1
What makes a grid coordinate a sufficient state for unrestricted right/up paths?
Question 2
Why does a no-consecutive-2s staircase need one extra bit of state?
Question 3
How do base cases and transitions together prove that a DP table is correct?
Choose one. Write an answer with a reason, then compare with a partner.
Reflect together
Make your thinking visible.
I used to think…
Name a claim or approach that changed.
Now I can explain…
Give the reason, not only the result.
I still wonder…
Write a question worth bringing to the next circle.
Share one sentence. Ask one follow-up question.
The idea to keep
A good state is a small summary that preserves every future-relevant choice.
Take a brute-force recurrence you know and ask what repeated subproblem could be stored. Then compare the number of states with the number of paths.
A good question belongs to everyone in the room.
1 / 21
← → to navigate and reveal · N for notes · F to present · Esc to exit