Define State and Transition
Name what dp[i] means precisely.
The Heart of DP
Every DP starts by naming a state: what does dp[i] actually represent? Get this sentence right and the rest follows.
State Must Be Precise
Write the meaning in words: dp[i] = the answer for the first i items. A fuzzy state definition leads to a buggy recurrence.
dp[i] = best total using items 0..i-1All lessons in this course
- Memoization vs Tabulation
- Define State and Transition
- Climbing Stairs & Coin Combinations
- Longest Increasing Subsequence