One decision per element

A shopkeeper on a street of n shops will pay you to clean their windows, but no two adjacent shops will both agree. Given what each shop pays, what is the most you can earn?

The instinct is to take every alternate shop. That fails on [5, 1, 1, 5]: alternating gives 6, and taking the first and last gives 10.

The decision

At each shop you have exactly two choices, so define the state by where you are:

best[i] = the most you can earn from shops 0..i

At shop i you either take it, which means you could not have taken i - 1, or you skip it and keep whatever i - 1 gave you:

best[i] = max(pay[i] + best[i - 2], best[i - 1])

That single line is the whole solution. Everything else is base cases.

The shape

This is the most common family in the subject. One dimension, one decision per element, and the state is usually "the best answer considering the first i things".

You will meet it as:

Recognising the family is most of the work, because the recurrence then almost writes itself.

Getting the state right

The state must carry everything that affects the future and nothing else. For the shops, knowing you are at shop i is enough. If the rule were "no three in a row", it would not be: you would also need to know how many you have just taken, and the state becomes best[i][taken_in_a_row].

That is how states grow, and why a second dimension appears. It is never decoration.