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 Palindrome Chamber.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Longest palindromic subsequence matches the clues
- 2Keep this true after every move: dp[left][right] is the longest palindromic subsequence inside that closed interval
- 3Reach the result within O(n squared) time and space
Rules and pressure
- Target cost: O(n squared) time and space
- State rule: dp[left][right] is the longest palindromic subsequence inside that closed interval
Lesson 1 of 3
Live algorithm trace
Longest palindromic subsequence
Complete execution1 of 6
b
left
b
b
a
b
Initialize all one-character intervals to length one.
1
single characters have length 12
grow interval lengths3
if ends match4
take inner length + 25
else max(drop left, drop right)6
return full intervalstring = bbbabdiagonal = 1
Truth to preserve / Cost target
Truth to preserve
dp[left][right] is the longest palindromic subsequence inside that closed interval
Cost target
O(n squared) time and space
An interval state asks for the best palindrome inside two boundaries. Equal ends wrap the inner answer; unequal ends discard one boundary and keep the better result.
Your call · What should guide every step of this algorithm?