作者簡介：大家好，我是未央；

博客首頁：未央.303

系列專欄：?？兔嬖嚤厮OP101

每日一句：人的一生，可以有所作為的時機只有一次，那就是現(xiàn)在！！！！！

文章目錄

前言

一、跳臺階

題目描述

題目解析

二、不同路徑的數(shù)目(一)

題目描述

題目解析

總結(jié)

---

---

前言

一、跳臺階

題目描述

描述：
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個 n 級的臺階總共有多少種跳法（先后次序不同算不同的結(jié)果）。

---

數(shù)據(jù)范圍：1≤n≤40

要求：時間復(fù)雜度：O(n)?，空間復(fù)雜度： O(1)。

---

示例1：

---

示例2：

---

題目解析

解題思路：

假設(shè)f[i]表示在第i個臺階上可能的方法數(shù)。逆向思維。如果我從第n個臺階進行下臺階，下一步有2中可能，一種走到第n-1個臺階，一種是走到第n-2個臺階。

所以f[n] = f[n-1] + f[n-2]. 那么初始條件了，f[0] = f[1] = 1。

所以就變成了：f[n] = f[n-1] + f[n-2], 初始值f[0]=1, f[1]=1，目標(biāo)求f[n] 。

---

和斐波那契數(shù)列的模式一樣。

---

代碼解析：

---

---

二、不同路徑的數(shù)目(一)

題目描述

描述：

一個機器人在m×n大小的地圖的左上角（起點）。

機器人每次可以向下或向右移動。機器人要到達地圖的右下角（終點）。

可以有多少種不同的路徑從起點走到終點？

備注：m和n小于等于100,并保證計算結(jié)果在int范圍內(nèi)；

---

數(shù)據(jù)范圍：0<n,m≤100，保證計算結(jié)果在32位整型范圍內(nèi)

要求：空間復(fù)雜度 O(nm)，時間復(fù)雜度 O(nm)

進階：空間復(fù)雜度 O(1)，時間復(fù)雜度O(min(n,m))

---

示例1：

---

示例2：

---

題目解析

解題思路：

首先我們在左上角第一個格子的時候，有兩種行走方式：如果向右走，相當(dāng)于后面在一個(n?1)?m的矩陣中查找從左上角到右下角的不同路徑數(shù)；而如果向下走，相當(dāng)于后面在一個n?(m?1)的矩陣中查找從左上角到右下角不同的路徑數(shù)。

而(n?1)?m的矩陣與n?(m?1)的矩陣都是n?m矩陣的子問題，因此可以使用遞歸。

---

解題步驟:

• step 1：（終止條件）?當(dāng)矩陣邊長n減少到1的時候，很明顯只能往下走，沒有別的選擇了，只有1條路徑；同理m減少到1時也是如此。因此此時返回數(shù)量為1.
• step 2：（返回值）?對于每一級都將其兩個子問題返回的結(jié)果相加返回給上一級。
• step 3：（本級任務(wù)）?每一級都有向下或者向右兩種路徑選擇，分別進入相應(yīng)分支的子問題。

代碼解析：

總結(jié)