【題目】
一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。
機(jī)器人每次只能向下或者向右移動(dòng)一步痪蝇。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）画株。
問(wèn)總共有多少條不同的路徑钝腺？
示例 1：
輸入： m = 3, n = 7
輸出： 28
示例 2：
輸入： m = 3, n = 2
輸出： 3
解釋：
從左上角開(kāi)始，總共有 3 條路徑可以到達(dá)右下角耘成。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
輸入： m = 7, n = 3
輸出： 28
示例 4：
輸入： m = 3, n = 3
輸出： 6
提示：
1 <= m, n <= 100- 題目數(shù)據(jù)保證答案小于等于
2 * 10^9
【題目解析】
解題方法
采用動(dòng)態(tài)規(guī)劃的思路榔昔，定義dp[i][j]為到達(dá)(i, j)位置的不同路徑的總數(shù)，那么可以得出狀態(tài)轉(zhuǎn)移方程為：dp[i][j] = dp[i-1][j] + dp[i][j-1]瘪菌，即到達(dá)某個(gè)格子的路徑數(shù)等于它上方格子的路徑數(shù)加上它左方格子的路徑數(shù)撒会。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# 初始化一個(gè)m*n的二維數(shù)組，所有值為1师妙。第一行和第一列的路徑數(shù)為1茧彤，因?yàn)樗鼈冎荒芤恢蓖禄蛲摇? dp = [[1]*n for _ in range(m)]
# 從(1, 1)開(kāi)始遍歷，因?yàn)?0, 0)為起始點(diǎn)疆栏，已經(jīng)初始化曾掂。
for i in range(1, m):
for j in range(1, n):
# 狀態(tài)轉(zhuǎn)移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 當(dāng)前點(diǎn)的路徑數(shù) = 從上方來(lái)的路徑數(shù) + 從左方來(lái)的路徑數(shù)
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 返回右下角點(diǎn)的路徑數(shù)
return dp[-1][-1]
執(zhí)行效率
【總結(jié)】
適用問(wèn)題類型
動(dòng)態(tài)規(guī)劃算法適用于多種類型的問(wèn)題，尤其是那些可以被分解為重疊子問(wèn)題的計(jì)數(shù)問(wèn)題壁顶、最值問(wèn)題珠洗、最優(yōu)解問(wèn)題等。"不同路徑"問(wèn)題是一個(gè)經(jīng)典的計(jì)數(shù)問(wèn)題若专，要求計(jì)算從網(wǎng)格的左上角到右下角的所有可能路徑數(shù)量许蓖。
解決算法：動(dòng)態(tài)規(guī)劃
算法特點(diǎn)：動(dòng)態(tài)規(guī)劃算法的核心特點(diǎn)在于解決了重疊子問(wèn)題，通過(guò)構(gòu)建DP表（通常是一維或二維數(shù)組）來(lái)保存子問(wèn)題的解调衰，避免了重復(fù)計(jì)算膊爪。同時(shí)，DP算法能夠提供一種系統(tǒng)的求解框架嚎莉，明確地定義狀態(tài)米酬、狀態(tài)轉(zhuǎn)移方程以及初始狀態(tài)和邊界條件。
-
時(shí)間復(fù)雜度與空間復(fù)雜度：
- 時(shí)間復(fù)雜度為
O(m*n)趋箩，其中m和n分別代表網(wǎng)格的行數(shù)和列數(shù)赃额。這是因?yàn)樾枰闅v整個(gè)網(wǎng)格一次加派，對(duì)每個(gè)格子計(jì)算到達(dá)它的路徑數(shù)量。 - 空間復(fù)雜度為
O(m*n)跳芳，主要空間開(kāi)銷來(lái)源于DP表的大小芍锦。在一些特殊情況下，通過(guò)狀態(tài)壓縮技巧可以將空間復(fù)雜度優(yōu)化到O(n)或O(m)飞盆。
- 時(shí)間復(fù)雜度為
實(shí)踐意義
動(dòng)態(tài)規(guī)劃算法在實(shí)踐中有著廣泛的應(yīng)用娄琉，能夠有效解決包括但不限于路徑計(jì)數(shù)、字符串處理吓歇、背包問(wèn)題等多種類型的問(wèn)題车胡。掌握動(dòng)態(tài)規(guī)劃不僅能夠幫助我們解決特定的算法題目，更能夠在面對(duì)實(shí)際編程和軟件開(kāi)發(fā)中的復(fù)雜問(wèn)題時(shí)照瘾，提供一種高效且系統(tǒng)的解決方案匈棘。學(xué)習(xí)和應(yīng)用動(dòng)態(tài)規(guī)劃，對(duì)于提升個(gè)人的問(wèn)題解決能力和編程能力都有顯著的幫助析命。
綜上所述主卫，動(dòng)態(tài)規(guī)劃作為一種強(qiáng)大的算法設(shè)計(jì)方法論，對(duì)于解決"不同路徑"這類問(wèn)題具有明顯的優(yōu)勢(shì)鹃愤，它通過(guò)優(yōu)化計(jì)算過(guò)程簇搅、減少不必要的計(jì)算，不僅提高了算法的執(zhí)行效率软吐，還增強(qiáng)了算法對(duì)于復(fù)雜問(wèn)題的處理能力瘩将。
