Problem context and objectives
Mission briefing
Dungeon strategy engineer · A robot must cross a tiled dungeon
Store enough solved tile states to plan the complete route: The Edit Forge.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Edit distance matches the clues
- 2Keep this true after every move: dp[i][j] is the minimum edits converting the first i characters to the first j characters
- 3Reach the result within O(mn) time and O(n) space
Rules and pressure
- Target cost: O(mn) time and O(n) space
- State rule: dp[i][j] is the minimum edits converting the first i characters to the first j characters
Lesson 1 of 3
Live algorithm trace
Edit distance
Complete execution1 of 6
h
source
o
r
s
e
r
Build the empty-source row from insertion counts.
1
base row costs 0 through n inserts2
for each source character3
start row with deletion cost4
if characters match: take diagonal5
else 1 + min(insert, delete, replace)6
return final distancesource = horsetarget = rosbase = [0,1,2,3]
Truth to preserve / Cost target
Truth to preserve
dp[i][j] is the minimum edits converting the first i characters to the first j characters
Cost target
O(mn) time and O(n) space
For two prefixes, equal final characters cost nothing. Otherwise insert, delete, or replace once after the cheapest neighboring prefix state.
Your call · What should guide every step of this algorithm?