Leetcode 62. Unique Paths - 程程下班學

Unique Paths : 機器人從最左上的格子到最右下的格子有多少種不同路徑，只能往下或往右走

Python

方法一 : 動態規劃

初始化一個全為1的m*n的陣列dp，遍歷除了第一行和第一列的所有元素，每個位置dp[i][j] = dp[i][j-1] + dp[i-1][j]表示起始位置到當前位置的不同路徑數等於從起始位置到左邊位置的不同路徑數加上從起始位置到上邊位置的不同路徑數，dp[-1][-1]來表示最尾端的位置及為解

class Solution(object):
    def uniquePaths(self, m, n):

        dp = [[1]*n for _ in range(m)]     #全為1的m*n的陣列dp
        for i in range(1,m):
            for j in range(1,n):
         #起始位置到左邊位置的不同路徑數加上從起始位置到上邊位置的不同路徑數
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[-1][-1]  #最尾端的位置

方法二 : 遞迴法

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return self.findPath(m, n, 1, 1)

    def findPath(self, m, n, row, col):
        if row == m and col == n: return 1
        if row > m or col > n: return 0
       #每一個格子的路徑=上方格子的路徑+左方格子的路徑
        return self.findPath(m, n, row, col + 1) + self.findPath(m, n, row + 1, col)

C++

動態規劃:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1)); // 初始化為1，因為第一行和第一列到達的路徑數都是1
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]; // 根據狀態轉移方程更新當前位置的路徑數
            }
        }
        
        return dp[m-1][n-1]; // 返回到達終點的路徑數
    }
};

Python

C++

相關