​LeetCode刷題實戰70:爬樓梯

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做 爬樓梯，我們先來看題面：

https://leetcode-cn.com/problems/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 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：2
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：3
輸出：3
解釋：有三種方法可以爬到樓頂。
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

解題

思路：可以這樣想，n個臺階，一開始可以爬 1 步，也可以爬 2 步，那麼n個臺階爬樓的爬樓方法就等於 一開始爬1步的方法數 + 一開始爬2步的方法數，這樣我們就只需要計算n-1個臺階的方法數和n-2個臺階方法數，同理，計算n-1個臺階的方法數只需要計算一下n-2個臺階和n-3個臺階，計算n-2個臺階需要計算一下n-3個臺階和n-4個臺階……

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

好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。