You are climbing a staircase. It takes n
steps to reach the top.
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
class Solution
{
//max stairs num is 45
array<int, 46> _storage = {0,1,2};
public:
//DP solution, O(n)
constexpr int climbStairs(int n)
{
if(!_storage[n])
_storage[n] = climbStairs(n-1) + climbStairs(n-2);
return _storage[n];
}
};