A dynamic-programming answer starts by defining what one stored result means. The recurrence is useful only after its state, base cases and dependency order are clear. A short formula without those details can hide counting errors.

This exercise counts ordered ways to reach a step using moves of one or two steps. It uses Python 3 and a deliberately simple problem so the reasoning can be checked by hand.

What does ways[i] represent?

It is the number of valid ordered move sequences whose total is exactly i. Reaching step i can finish with a one-step move from i−1 or a two-step move from i−2. Those final moves separate the cases, so their counts can be added.

def count_ways(steps):
    if steps < 0:
        raise ValueError("steps must be nonnegative")
    ways = [0] * (steps + 1)
    ways[0] = 1
    for current in range(1, steps + 1):
        ways[current] += ways[current - 1]
        if current >= 2:
            ways[current] += ways[current - 2]
    return ways[steps]

assert count_ways(0) == 1
assert count_ways(1) == 1
assert count_ways(2) == 2
assert count_ways(4) == 5

For four steps, the sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2. Order matters in this task. If the task counted unordered combinations, this recurrence would need a different interpretation.

Why does the zero-step case have one way?

There is one empty sequence that makes a total of zero. This base case allows a final move to extend a valid beginning. Setting it to zero would remove those constructions from later states.

Zero as a valid input is different from a negative request. The sample rejects negative input explicitly instead of returning a plausible-looking count. State that input contract before discussing the recurrence.

Why calculate states in increasing order?

Each state depends on smaller states that are already computed. Bottom-up order makes those dependencies available. A top-down implementation with memoization could express the same subproblems, but it would have different call-stack behavior.

Calling the same recursive subproblem many times without storing its result can repeat large amounts of work. Dynamic programming is about recognizing and reusing those results, not merely using recursion or an array.

Can the space be reduced?

For this recurrence, the next result only needs the previous two counts. A rolling pair can reduce auxiliary storage when only the final count is required. If the caller needs the whole table or an actual move sequence, keeping more information can be useful.

Do not remove the table before understanding the state. Space optimization is easier to explain once the unoptimized recurrence is correct and tested.

How should complexity be described?

The table performs a linear number of state updates and stores a linear number of counts. For an interview's fixed-cost arithmetic model, that gives linear time and space in the number of steps. Very large exact counts have growing integer sizes, so a detailed numeric-cost analysis would need to account for that as well.

A modulo requirement is another contract change. It alters the stored values while preserving a counting relation under the chosen arithmetic. Do not add a modulus unless the problem requests one.

How can you verify the recurrence?

  • Enumerate short sequences by hand.
  • Check the empty and one-step cases before larger ones.
  • Use a small brute-force generator as a reference.
  • State whether order matters and whether repeated moves are allowed.
  • Test any input rejection separately from valid counts.

For a follow-up, allow moves of one or three steps. Define the state again, change the predecessor choices and recalculate the first few values. The point is to derive the answer from the new rules, not recognize a familiar sequence and hope it still applies.

References and next practice

ocw.mit.edu — algorithms

Browse interview topics · Practise a question in Interview Challenge · How to Answer Technical Interview Questions Out Loud