leetCode，LeetCode62 Unique Paths

2023-11-07 阅读 28 评论 0

摘要：題目： leetCode，A robot is located at the top-left corner of a?m?x?n?grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the

題目：

leetCode，A robot is located at the top-left corner of a?m?x?n?grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there? （Medium）

Above is a 3 x 7 grid. How many possible unique paths are there?

Note:?m?and?n?will be at most 100.

分析：

今天時間比較晚了，先寫兩道比較熟悉的題目吧。

典型的矩陣型動態規劃，dp[i][j]定義為到當前節點的...（視題目而定）。

所以本題dp[i][j]表示到當前節點的不同路徑數。則第一行全為1，第一列全為1。

后續的 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

 1 class Solution {
 2 public:
 3     int uniquePaths(int m, int n) {
 4         int dp[m][n] = {0};
 5         dp[0][0] = 1;
 6         for (int i = 0; i < n; ++i) {
 7             dp[0][i] = 1;
 8         }
 9         for (int i = 0; i < m; ++i) {
10             dp[i][0] = 1;
11         }
12         for (int i = 1; i < m; ++i) {
13             for (int j = 1; j < n; ++j) {
14                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
15             }
16         }
17         return dp[m - 1][n - 1];
18     } 
19 };