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 Subsequence Count.
A greedy step can trap the robot; recomputing every route is too expensive.
How you win
- 1Recognize when Distinct subsequences matches the clues
- 2Keep this true after every move: dp[j] counts ways the processed source prefix forms the first j target 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[j] counts ways the processed source prefix forms the first j target characters
Lesson 1 of 3
Live algorithm trace
Distinct subsequences
Complete execution1 of 5
r
source
a
b
b
b
i
Seed the empty target with one alignment.
1
dp[0] = 12
scan source characters3
scan target backward4
if characters match5
dp[j + 1] += dp[j]6
return dp[target length]source = rabbbittarget = rabbitdp0 = 1
Truth to preserve / Cost target
Truth to preserve
dp[j] counts ways the processed source prefix forms the first j target characters
Cost target
O(mn) time and O(n) space
A source character may be skipped, or if it matches the next target character, used to extend every prior alignment. Reverse target iteration prevents reusing one source character twice.
Your call · What should guide every step of this algorithm?