Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Square Tiles.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Perfect squares matches the clues
- 2Keep this true after every move: dp[total] is the minimum square count that sums exactly to total
- 3Reach the result within O(n square root n) time and O(n) space
Rules and pressure
- Target cost: O(n square root n) time and O(n) space
- State rule: dp[total] is the minimum square count that sums exactly to total
Lesson 1 of 3
Live algorithm trace
Perfect squares
Complete execution1 of 6
Seed total zero with no squares.
1
dp[0] = 02
for total from 1 through n3
try square = k*k <= total4
candidate = dp[total - square] + 15
keep the fewest6
return dp[n]dp0 = 0
Truth to preserve / Cost target
Truth to preserve
dp[total] is the minimum square count that sums exactly to total
Cost target
O(n square root n) time and O(n) space
Every positive total ends with some square not exceeding it. Extend the best solution for the remaining total and choose the fewest tiles.
Your call · What should guide every step of this algorithm?