【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];
    }
};