題目

一個機器人位于一個?m x n?網格的左上角 （起始點在下圖中標記為 “Start” ）。

機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中標記為 “Finish” ）。

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

示例

示例 1：

輸入：m = 3, n = 7
輸出：28

示例 2：

輸入：m = 3, n = 2
輸出：3
解釋：
從左上角開始，總共有 3 條路徑可以到達右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

輸入：m = 7, n = 3
輸出：28

示例 4：

輸入：m = 3, n = 3
輸出：6

分析

動態規劃

算法思路

設?dp[i][j]?表示機器人到達第?i?行第?j?列網格的不同路徑數量。

邊界條件：

• 當機器人位于第一行時，由于它只能從左邊的網格向右移動到達，所以對于第一行的任意列?j，都有?dp[0][j] = 1。
• 當機器人位于第一列時，由于它只能從上方的網格向下移動到達，所以對于第一列的任意行?i，都有?dp[i][0] = 1。

狀態轉移方程：

• 對于其他位置?(i, j)（i > 0?且?j > 0），機器人可以從上方的網格?(i - 1, j)?向下移動一步到達，也可以從左邊的網格?(i, j - 1)?向右移動一步到達。因此，到達?(i, j)?的不同路徑數量等于到達?(i - 1, j)?的路徑數量加上到達?(i, j - 1)?的路徑數量，即?dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

最終結果：

• 要求的是機器人到達右下角網格?(m - 1, n - 1)?的不同路徑數量，即?dp[m - 1][n - 1]。

時間復雜度：O()

空間復雜度：O()

class Solution {
public:int uniquePaths(int m, int n) {// 創建一個二維數組 dp 來存儲到達每個網格的不同路徑數量std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));// 初始化第一行，因為從起點到第一行的任意位置都只有一種路徑（一直向右走）for (int j = 0; j < n; ++j) {dp[0][j] = 1;}// 初始化第一列，因為從起點到第一列的任意位置都只有一種路徑（一直向下走）for (int i = 0; i < m; ++i) {dp[i][0] = 1;}// 填充 dp 數組，根據狀態轉移方程計算到達每個位置的不同路徑數量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];}
};