DP Pattern and Importance

Every 1D DP problem follows the same $4$-step pattern:

$1.$ Define your state

$2.$ Write the transition (how to compute each state from previous states)

$3.$ Set base cases

$4.$ Extract the answer. $\Rightarrow$If your DP state is wrong, the entire solution breaks. Design it carefully so it captures all the information you need. Before I show you the first problem, pause and think: for House Robber, what information do you need at each step to make the right choice? Let us start with House Robber, a classic problem from Leetcode.