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 Common Signal.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Longest common subsequence matches the clues
- 2Keep this true after every move: dp[i][j] is the LCS length of the first i and 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 LCS length of the first i and j characters
Lesson 1 of 3
Live algorithm trace
Longest common subsequence
Complete execution1 of 5
a
first
b
c
a
c
Start with empty-prefix base states.
1
dp = zeros for the second string2
for each character in first3
scan characters in second4
if equal: next = diagonal + 15
else: next = max(top, left)6
return final statefirst = abcsecond = acdp = [0,0,0]
Truth to preserve / Cost target
Truth to preserve
dp[i][j] is the LCS length of the first i and j characters
Cost target
O(mn) time and O(n) space
A state for two prefixes records their longest common subsequence length. Matching final characters extend the diagonal; a mismatch discards one side and keeps the better result.
Your call · What should guide every step of this algorithm?