Counting the ways to reach a target by small steps is the gentlest DP problem and the best place to learn how to set up a recurrence. Thinking about the last move gives ways(n) = ways(n-1) + ways(n-2), which is Fibonacci. The same pattern counts ways to make change or decode a message. Since only the last two values matter, two variables replace the whole array.