當前位置:網站首頁>力扣——每日一題——爬樓梯

力扣——每日一題——爬樓梯

2022-01-26 23:45:54 愛編程的暉哥

題目來源於力扣——70. 爬樓梯 (medium) - 爬樓梯 - 力扣(LeetCode) (leetcode-cn.com)

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢?

注意:給定 n 是一個正整數。

示例 1:

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

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

大家做這題之前可以先了解一下斐波那契數列

給一個如下的數列

0  1   1   2   3    5   8   13    21    34

大家可以通過觀察可以發現,都能第三項開始,每一項都等於前面兩項的和,

也就是說:第三項  1=0+1

                  第四項   2=1+1

                  第五項   3=1+2

                          ……

 想要求出這個數列的第n項,我們就要知道第n項的前一項和前兩項。

其實求爬臺階也是這個道理,我們要知道爬到第n個臺階有多少中跳法,只要知道第n個臺階前一個臺階的爬法和前兩個臺階的爬法就可以了。

其實就是這樣:

  1. 爬上 n−1 階樓梯的方法數量。因為再爬1階就能到第n階
  2. 爬上 n−2 階樓梯的方法數量,因為再爬2階就能到第n階

只要把爬到n-1階樓梯和爬到n-2階樓梯的方法數量相加就是爬到n階樓梯的方法數量了

代碼如下:

#include<stdio.h>
int fib(int n)
{
    //為爬前兩級臺階的方法賦值
	int a = 1;   //爬第一級臺階有一種方法
	int b = 2;   //爬第二級臺階有兩種方法
	int c = 0;   //求第n級臺階的前兩級和前一級臺階的方法的和
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
int main()
{
	int n = 0;
	scanf_s("%d", &n);
	int ret = fib(n);
	printf("%d", ret);
	return 0;
}

版權聲明
本文為[愛編程的暉哥]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201262345539947.html

隨機推薦