Given n, return the number of ways to reach step n if you may climb 1, 2, or 3 steps at a time. Pattern focus: Climbing stairs. This is a direct extension of the classic staircase recurrence into three previous states.
n = target stair index
number of distinct ways to reach step n
Example 1:
Input:
n = 4
Output:
7
Explanation:
Ways: 1111, 112, 121, 13, 211, 22, 31.
Example 2:
Input:
n = 3
Output:
4
Explanation:
Ways: 111, 12, 21, 3.