070.md

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?

Note: Given n will be a positive integer.

example1:
Input: 2
Output:  2
Explanation:  There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

example2:
Input: 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

思路

   1阶梯返回1，二阶梯返回2 大于2时：
   
   n高的楼梯可以走的方式等于 n-1高的楼梯可以走的数量 加上 n-2高的楼梯可走的数量。

总结

    dp问题，问题的结果依赖于子问题。走到n阶楼梯依赖于n-1阶梯和n-2阶梯的结果。
    所以需要保存两个变量即可。
    part1：检测特殊输入。
        if n <= 1 {
            return 1
        }
    part2: 初始化变量。
        twoStep, oneStep := 1, 1
    part3: 实现递归式。
        for i := 2; i <= n; i++ {
            oneStep, twoStep =  twoStep + oneStep, oneStep
        }
    part4: 返回结果。
        return oneStep

代码

class Solution {
public:
    int climbStairs(int n) {
        vector<int> climb = {0,1,2};
        if(n==1 || n==0) return climb[1];
        if(n==2) return climb[2];
        
        for(int i=3;i<=n;++i){
            climb.push_back(climb[i-1]+climb[i-2]);
        }
        
        return climb.back();
    }
};

func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    twoStep, oneStep := 1, 1
    for i := 2; i <= n; i++ {
        oneStep, twoStep =  twoStep + oneStep, oneStep
        
    }
    return oneStep
}