LeetCode初級(jí)算法--動(dòng)態(tài)規(guī)劃01：爬樓梯

一、引子

這是由LeetCode官方推出的的經(jīng)典面試題目清單~
這個(gè)模塊對(duì)應(yīng)的是探索的初級(jí)算法~旨在幫助入門算法。我們第一遍刷的是leetcode推薦的題目。

二、題目

假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個(gè)正整數(shù)。

示例1:

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

示例2:

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

1、思路

首先我可以確切的告訴你，這種簡(jiǎn)單的爬樓梯也是一個(gè)斐波那契數(shù)列，不信你自己從簡(jiǎn)單的數(shù)1，2，3..自己推論一下。

接著，我們來討論一般情況。我們把n級(jí)臺(tái)階時(shí)的跳法看成是n的函數(shù)，記為f(n)。當(dāng)n>2時(shí)，第一次跳的時(shí)候就有兩種不同的選擇：一是第一次只跳1級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-1級(jí)臺(tái)階的跳法數(shù)目，即為f(n-1)；另外一種選擇是跳一次跳2級(jí)，此時(shí)跳法數(shù)目等于后面剩下的n-2級(jí)臺(tái)階的跳法數(shù)目，即為f(n-2)。因此n級(jí)臺(tái)階的不同跳法的總數(shù)f(n)=f(n-1)+f(n-2)。分析到這里，我們不難看出這實(shí)際上就是斐波那契數(shù)列了。

2、編程實(shí)現(xiàn)

python

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

本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！

審核編輯 黃昊宇