Know this before you start: “Define the state: what does dp[i] mean?”

Defining the DP state

Before any code, finish the sentence “dp[i] is …”. The recurrence, base cases and loop order all follow from that sentence.

The idea

Dynamic programming reuses answers to smaller versions of the problem. The hard part is deciding what “a smaller version” is. Write it as a sentence: “dp[i] = the most money I can rob from the first i houses.”

Then ask: how does dp[i] follow from earlier entries (the transition)? What are the smallest cases (base cases)? What's the final answer (often dp[n])?

See it step by step

House Robber on [2, 7, 9, 3, 1]

State: dp[i] = best total from houses 0..i.
Transition: skip house i (dp[i − 1]) or rob it (dp[i − 2] + value). Take the bigger.
dp = 2, 7, 11, 11, 12 → answer 12 (2 + 9 + 1).

In code (Python)

def rob(houses):
    if not houses:
        return 0
    dp = [0] * len(houses)
    dp[0] = houses[0]
    for i in range(1, len(houses)):
        take = houses[i] + (dp[i - 2] if i >= 2 else 0)
        dp[i] = max(dp[i - 1], take)
    return dp[-1]

print(rob([2, 7, 9, 3, 1]))   # 12

Usually (number of states) × (work per state): here O(n).

When you'll use it

“How many ways”, “minimum cost”, “maximum value”, “is it possible” where choices now affect later ones.

Common mistakes

Coding before you can state what dp[i] means.
Base cases that don't match the sentence (dp[0] vs dp[1]).