LeetCode初級演算法--動態規劃01：爬樓梯

搜索微信公眾號:'AI-ming3526'或者'計算機視覺這件小事' 獲取更多演算法、機器學習干貨
csdn：https://blog.csdn.net/baidu_31657889/
csdn：https://blog.csdn.net/abcgkj/
github：https://github.com/aimi-cn/AILearners

一、引子

這是由LeetCode官方推出的的經典面試題目清單~
這個模塊對應的是探索的初級演算法~旨在幫助入門演算法，我們第一遍刷的是leetcode推薦的題目，
查看完整的劍指Offer演算法題決議請點擊github鏈接：
github地址

二、題目

假設你正在爬樓梯，需要 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、編程實作

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

AIMI-CN AI學習交流群【1015286623】獲取更多AI資料

分享技術，樂享生活：我們的公眾號計算機視覺這件小事每周推送“AI”系列資訊類文章，歡迎您的關注！

本文由博客一文多發平臺 OpenWrite 發布！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65606.html

標籤：其他

上一篇：LeetCode初級演算法--排序和搜索01：第一個錯誤的版本

下一篇：最小二乘法