Total number of ways to climb staircase using dynamic programming

Question

Given staircase of length $13$ and up to $3$ steps to climb at a time, in how many ways can a person reach the top?

Suppose we are at the top $S(13)$, one can reach here in three ways and that's from $S(12)$, $S(11)$ and $S(10)$. We can climb $1$ step from $S(12)$, $2$ steps from $S(11)$ and $3$ steps from $S(10)$. Those $1$, $2$ and $3$ steps can be climbed in $S(1)$, $S(2)$ and $S(3)$, respectively.

So, shouldn't the solution to the problem be:

$$S(13) = (S(12) + S(1)) + (S(11) + S(2)) + (S(10) + S(3))$$

How can it be just $S(13) = S(12) + S(11) + S(10)$?

Answer 1

The ways have to be disjoint in order for you to add them up. When the last step is from staircase 10,11 or 12, they are disjoint cases because in one step you reach S13. What you are doing instead is: when at stair-case 10, you are including in its count, the path where you go from 10 to 11 and 11 to 13. But this is actually captured in the case where the last step was from 11.

Answer 2

You have counted various histories several times. Instead convince yourself that $$S(0)=S(1)=1, \quad S(2)=2\ ,$$ and for $n\geq3$ note that the first step can be any one from $\{1,2,3\}$. It follows that $$S(n)=S(n-1)+S(n-2)+S(n-3)\qquad(n\geq3)\ ,\tag{1}$$ according to the first decision made. I suggest that you use $(1)$ recursively with pencil and paper, since the "Master Theorem" for this recursion leads to complicated expressions involving irrational and complex solutions of a third degree equation.