LeetCode初級算法--動態規劃01:爬樓梯
一、引子
這是由LeetCode官方推出的的經典面試題目清單~
這個模塊對應的是探索的初級算法~旨在幫助入門算法。我們第一遍刷的是leetcode推薦的題目。
二、題目
假設你正在爬樓梯。需要 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 階
1、思路
首先我可以確切的告訴你,這種簡單的爬樓梯也是一個斐波那契數列,不信你自己從簡單的數1,2,3..自己推論一下。
接著,我們來討論一般情況。我們把n級臺階時的跳法看成是n的函數,記為f(n)。當n>2時,第一次跳的時候就有兩種不同的選擇:一是第一次只跳1級,此時跳法數目等于后面剩下的n-1級臺階的跳法數目,即為f(n-1);另外一種選擇是跳一次跳2級,此時跳法數目等于后面剩下的n-2級臺階的跳法數目,即為f(n-2)。因此n級臺階的不同跳法的總數f(n)=f(n-1)+f(n-2)。分析到這里,我們不難看出這實際上就是斐波那契數列了。
2、編程實現
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 1
a = 1
b = 1
for i in range(1,n):
a , b = b , a+b
return b
本文由博客一文多發平臺 OpenWrite 發布!
審核編輯 黃昊宇
-
人工智能
+關注
關注
1804文章
48737瀏覽量
246664 -
機器學習
+關注
關注
66文章
8492瀏覽量
134122 -
深度學習
+關注
關注
73文章
5555瀏覽量
122498 -
leetcode
+關注
關注
0文章
20瀏覽量
2429
發布評論請先 登錄
Google日本子公司Schaft發布人形兩足機器人
LabVIEW中時怎么導入圖片的?
動態規劃算法和貪心算法的區別與聯系

這款爬樓快遞機器人,可以讓你不用下樓,快遞直接送進家
能爬樓梯的快遞機器人如果量產 快遞小哥真的要失業了
如何實現雙足機器人爬樓梯的步態規劃與參數優化

自動調整平衡的爬樓梯機器人設計
如何利用Arduino UNO制作一個爬樓梯機器人

評論