# Total number of ways to climb staircase using dynamic programming

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)$?

• Break down the cases by size of the last "step". Commented Aug 2, 2016 at 15:14
• The same (incorrect) reasoning would suggest $$S(4)=(S(3)+S(1))+(S(2)+S(2))+(S(1)+S(3))$$ Can you see why that doesn't make sense? Commented Aug 2, 2016 at 15:19
• To follow on from @hardmath, when you say '2 steps from Step 11' you mean 'we have advanced by a double-step, and therefore came from Step 11'. Having advanced by a double-step disallows some of S(11) + S(2) because S(2) includes single-steps.
– Shai
Commented Aug 2, 2016 at 15:37
• I narrowed it down to S(2) with only 1 ways to reach where S(1)=1. Hence, S(2) can be reached only from S(1) making S(2)=S(1). Now I get it, why we shouldn't take the count of steps from Step1 i.e, S(2)=S(1)+S(1)=2 which is incorrect. Commented Aug 2, 2016 at 16:16

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.