不同路徑

題目描述：一個機器人位于一個 m x n 網(wǎng)格的左上角 （起始點在下圖中標(biāo)記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。

問總共有多少條不同的路徑？

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/unique-paths/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：遞歸法

首先，經(jīng)過分析可知，到達(dá)任意一個單元格子的最后一步，可以從這個格子的左邊過來，也可以從這個格子的上邊過來，所以到達(dá)任意一個格子的步數(shù)是到它左邊的步數(shù)加上到它上面格子的步數(shù)之和，所以可以用遞歸的方法求解，具體過程如下：

• 如果m等于1或者n等于1，直接返回1；

• 如果上面的條件不滿足，則遞歸調(diào)用該方法求解uniquePaths(m - 1, n) + uniquePaths(m, n - 1)。

解法二：迭代法

首先記錄第一行的格子的數(shù)字都是1，然后由于第一列的值都是1，而下面的每一行的1 ~ n-1列的值都可以根據(jù)當(dāng)前行的左邊的格子和上一行的上面的格子的值相加所得，所以通過迭代得到每一行的值，最后返回最后一行的最后一個值即為最終結(jié)果。

【每日寄語】 給自己信心，沒有人可以幫你，不鉆牛角尖，自然就海闊天空！