Core pattern
Prefix / Split DP
Step 4 of 14Pattern 2 of 7
×How to recognize it fast
Use this pattern when you are solving a string or prefix by trying every possible cut point before the current position.
When you see
break stringdecode digitspartition prefixcan form stringnumber of ways to split
Think
- Let me solve the first i characters.
- For every position i, I should try all possible previous cut points j -> i.
What to do once the pattern is clear
Core trick
- Define dp[i] as the answer for the first i characters.
- At each position, try every valid previous cut.
- If substring checks are expensive, precompute or cache them early.
Shortcut recognition
Split string into valid partsPrefix can be formedCount ways to decode or partition
Hidden trick
Always watch for invalid zero cases, dictionary lookup costs, and palindrome precomputation if the question keeps asking about ranges.
Common definition
dp[i] = answer for the prefix s[0..i)