今天是紀錄LeetCode解題的第六十二天

第六十二題題目：There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

有一個機器人在m * n的網格上，機器人初始在左上角(即grid[0][0])，機器人嘗試走到右下角(grid[m - 1][n - 1])，在任何時刻機器人只能向下或向右移動

給定兩個正整數m、n，返回機器人到達右下角可能的唯一路徑數量

產生的測試案例使得答案小於或等於2 * 10^9

解題思路

這題是一題比較簡單的DP題目，我們可以先嘗試寫出DP表格，推論出它的轉移方程式，首先我們可以發現當1 * n或m * 1時，都只會有一種路徑走法，所以程式一開始可以先初始化DP表格中row、col等於0時路徑數量等於1，接著我們看2 * 2的情況會有2種路徑走法，所以可以得知DP[1][1] = DP[0][1] + DP[1][0]，也就是說到達某一格的路徑數量等於它的上一row數量加上左邊一col的數量，推論出轉移方程式為
DP[row][col] = DP[row-1][col] + DP[row][col-1]

DP表格

此DP表格row = 1、col = 1就表示m * n = 2 * 2時的路徑有兩條，而4 * 4則看DP表格中row = 3、col = 3時共有20條路徑
如果row = 1、col = 2時，我們想走到這個位置，會經過row = 0、col = 2，而經過這個點的路徑只有一條；也會經過row = 1、col = 1這個點，而到1、1這個點則可以走0、1或1、0共兩種走法，所以最後要到row = 1、col = 2就是把上述走法加起來為1 + 2 = 3，這就是狀態轉移方程式推論過程由來

程式碼

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        #初始化當row或col為1時皆只有一條路徑
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        for r in range(1,m):
            for c in range(1,n):
                dp[r][c] = dp[r-1][c] + dp[r][c-1]
        return dp[m-1][n-1]

明天的題目是這題的變化題，可以先思考一下如果grid上出現障礙物的話，該怎麼計算路徑數並推導出轉移方程式