Leetcode 070 Climbing Stairs

Leetcode 070 题

Difficulty:Easy

Tag: Dynamic Programming, Fibonacci

Climbing Stairs

题目原址：https://leetcode.com/problems/climbing-stairs/?tab=Description

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?

大意：假设你在爬楼梯，总共需要爬$n$个台阶才能到达顶部，但是一次只能爬一个或两个台阶，那么可以有多少种方式爬到顶部？

思路

先从最基础的开始：

if n <= 0, 爬楼梯的方式为 0
if n == 1, 爬楼梯的方式为 1
if n == 2, 爬楼梯的方式为 2 一次爬两个台阶 和 一次爬两个台阶爬两次

再来看结束的情况：

现在给定了总的台阶数n,如果我们知道爬到 第$n - 1$个台阶, 和 第$n - 2$个台阶的方式分别为 n1个, n2个，那么到达第 $n$ 个台阶的方式应该为 $n_1 + n_2$个

因为在 第$n - 1$个台阶时，只需要上一个台阶就可以到达 第 $n$ 个台阶

在 第 $n - 2$ 个台阶时，只需要上一次上两个台阶就可以到达 第 $n$ 个台阶

其实，分析到这里的时候，是不是有种似曾相识的感觉，是不是有斐波那契数列的影子，只不过数列开始前两项不是 1，1 而是 1， 2，但是满足斐波那契数列的性质–当前项的值为前两项的和。

所以，也就衍生出了第二种解法，就利用这种性质。

动态规划解法

设 $dp[i]$为到达第$i$个台阶的方式数

递推方程：

\(dp(i) = \begin{cases} dp[1] = 1, & \text{ i = 1} \\ dp[2] = 2, & \text{ i = 2 } \\ dp[i] = dp[i-1] + dp[i - 2], & \text{ i $\gt$ 2 } \end{cases}\)

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

斐波那契解法

其实就是构造数组的过程

可以采用递归的构造方法，亦可以是迭代的构造方法

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int oneStep = 2;
        int twoStep = 1;
        int allStep = 0;
        for(int i = 2; i < n; i++)
        {
            allStep = oneStep + twoStep;
            twoStep = oneStep;
            oneStep = allStep;
        }
        return allStep;
    }
};