【LeetCode】70. Climbing Stairs

问题描述

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

跳楼梯，每次可以跳1阶或2阶，问跳到第n阶有多少种方法？

问题分析

设f(n)为跳到n阶时的方法，则有：

• f(0) = 0,
• f(1) = 1, 只能选择跳1阶
• f(2) = 2, 两种方法：1次跳1阶，跳两次；一次直接跳2阶

到f(3)就方便了，n=3时，之前他可能是通过跳1阶上来的，则之前跳楼梯的方法数为f(n-1)；之前也有可能是跳两阶上来的，方法数为f(n-2)。总数就为：f(n)=f(n-1)+f(n-2)

代码

class Solution {
public:
    int climbStairs(int n) {
        int v[n+3];
		v[0] = 0;
		v[1] = 1;
		v[2] = 2;
		for(int i=3;i<n+3;i++) {
			v[i] = v[i-1]+v[i-2];	
		}
		return v[n];
    }
};