?LeetCode刷題實(shí)戰(zhàn)70：爬樓梯

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問(wèn)題叫做?爬樓梯，我們先來(lái)看題面：

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
輸出：2
解釋：有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階

示例 2：

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

解題

本題可以利用動(dòng)態(tài)規(guī)劃解決 。

思路：可以這樣想，n個(gè)臺(tái)階，一開(kāi)始可以爬 1 步，也可以爬 2 步，那么n個(gè)臺(tái)階爬樓的爬樓方法就等于 一開(kāi)始爬1步的方法數(shù) + 一開(kāi)始爬2步的方法數(shù)，這樣我們就只需要計(jì)算n-1個(gè)臺(tái)階的方法數(shù)和n-2個(gè)臺(tái)階方法數(shù)，同理，計(jì)算n-1個(gè)臺(tái)階的方法數(shù)只需要計(jì)算一下n-2個(gè)臺(tái)階和n-3個(gè)臺(tái)階，計(jì)算n-2個(gè)臺(tái)階需要計(jì)算一下n-3個(gè)臺(tái)階和n-4個(gè)臺(tái)階……

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

好了，今天的文章就到這里，如果覺(jué)得有所收獲，請(qǐng)順手點(diǎn)個(gè)在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動(dòng)力。