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

博客首頁：未央.303

系列專欄：牛客面試必刷TOP101

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

文章目錄

前言

一、跳臺(tái)階

題目描述

題目解析

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

題目描述

題目解析

總結(jié)

---

---

前言

一、跳臺(tái)階

題目描述

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

---

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

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

---

示例1：

---

示例2：

---

題目解析

解題思路：

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

所以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ù)目(一)

題目描述

描述：

一個(gè)機(jī)器人在m×n大小的地圖的左上角（起點(diǎn)）。

機(jī)器人每次可以向下或向右移動(dòng)。機(jī)器人要到達(dá)地圖的右下角（終點(diǎn)）。

可以有多少種不同的路徑從起點(diǎn)走到終點(diǎn)？

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

---

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

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

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

---

示例1：

---

示例2：

---

題目解析

解題思路：

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

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

---

解題步驟:

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

代碼解析：

總結(jié)