Skip to content

Commit 211df55

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0062. Unique Paths
1 parent 0bc7115 commit 211df55

File tree

9 files changed

+142
-53
lines changed

9 files changed

+142
-53
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -189,6 +189,7 @@
189189
- [三角形最小路径和](./solution/0100-0199/0120.Triangle/README.md)
190190
- [矩阵区域和](./solution/1300-1399/1314.Matrix%20Block%20Sum/README.md)
191191
- [二维区域和检索 - 矩阵不可变](./solution/0300-0399/0304.Range%20Sum%20Query%202D%20-%20Immutable/README.md)
192+
- [不同路径](./solution/0000-0099/0062.Unique%20Paths/README.md)
192193
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
193194
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
194195
- [最长上升子序列](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -183,6 +183,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
183183
- [Triangle](./solution/0100-0199/0120.Triangle/README_EN.md)
184184
- [Matrix Block Sum](./solution/1300-1399/1314.Matrix%20Block%20Sum/README_EN.md)
185185
- [Range Sum Query 2D - Immutable](./solution/0300-0399/0304.Range%20Sum%20Query%202D%20-%20Immutable/README_EN.md)
186+
- [Unique Paths](./solution/0000-0099/0062.Unique%20Paths/README_EN.md)
186187
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
187188
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)
188189
- [Russian Doll Envelopes](./solution/0300-0399/0354.Russian%20Doll%20Envelopes/README_EN.md)

‎solution/0000-0099/0062.Unique Paths/README.md

Lines changed: 62 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -54,27 +54,87 @@
5454
<li>题目数据保证答案小于等于 <code>2 * 10<sup>9</sup></code></li>
5555
</ul>
5656

57-
5857
## 解法
5958

6059
<!-- 这里可写通用的实现逻辑 -->
6160

61+
动态规划。
62+
63+
假设 `dp[i][j]` 表示到达网格 `(i,j)` 的路径数，则 `dp[i][j] = dp[i - 1][j] + dp[i][j - 1]`。
64+
6265
<!-- tabs:start -->
6366

6467
### **Python3**
6568

6669
<!-- 这里可写当前语言的特殊实现逻辑 -->
6770

6871
```python
69-
72+
class Solution:
73+
def uniquePaths(self, m: int, n: int) -> int:
74+
dp = [[1] * n for _ in range(m)]
75+
for i in range(1, m):
76+
for j in range(1, n):
77+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
78+
return dp[m - 1][n - 1]
7079
```
7180

7281
### **Java**
7382

7483
<!-- 这里可写当前语言的特殊实现逻辑 -->
7584

7685
```java
86+
class Solution {
87+
public int uniquePaths(int m, int n) {
88+
int[][] dp = new int[m][n];
89+
for (int i = 0; i < m; ++i) {
90+
Arrays.fill(dp[i], 1);
91+
}
92+
for (int i = 1; i < m; ++i) {
93+
for (int j = 1; j < n; ++j) {
94+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
95+
}
96+
}
97+
return dp[m - 1][n - 1];
98+
}
99+
}
100+
```
101+
102+
### **C++**
103+
104+
```cpp
105+
class Solution {
106+
public:
107+
int uniquePaths(int m, int n) {
108+
vector<vector<int>> dp(m, vector<int>(n, 1));
109+
for (int i = 1; i < m; ++i) {
110+
for (int j = 1; j < n; ++j) {
111+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
112+
}
113+
}
114+
return dp[m - 1][n - 1];
115+
}
116+
};
117+
```
77118
119+
### **Go**
120+
121+
```go
122+
func uniquePaths(m int, n int) int {
123+
dp := make([][]int, m)
124+
for i := 0; i < m; i++ {
125+
dp[i] = make([]int, n)
126+
}
127+
for i := 0; i < m; i++ {
128+
for j := 0; j < n; j++ {
129+
if i == 0 || j == 0 {
130+
dp[i][j] = 1
131+
} else {
132+
dp[i][j] = dp[i-1][j] + dp[i][j-1]
133+
}
134+
}
135+
}
136+
return dp[m-1][n-1]
137+
}
78138
```
79139

80140
### **...**

‎solution/0000-0099/0062.Unique Paths/README_EN.md

Lines changed: 58 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -52,21 +52,77 @@ From the top-left corner, there are a total of 3 ways to reach the bottom-right
5252
<li>It&#39;s guaranteed that the answer will be less than or equal to <code>2 * 10<sup>9</sup></code>.</li>
5353
</ul>
5454

55-
5655
## Solutions
5756

5857
<!-- tabs:start -->
5958

6059
### **Python3**
6160

6261
```python
63-
62+
class Solution:
63+
def uniquePaths(self, m: int, n: int) -> int:
64+
dp = [[1] * n for _ in range(m)]
65+
for i in range(1, m):
66+
for j in range(1, n):
67+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
68+
return dp[m - 1][n - 1]
6469
```
6570

6671
### **Java**
6772

6873
```java
74+
class Solution {
75+
public int uniquePaths(int m, int n) {
76+
int[][] dp = new int[m][n];
77+
for (int i = 0; i < m; ++i) {
78+
Arrays.fill(dp[i], 1);
79+
}
80+
for (int i = 1; i < m; ++i) {
81+
for (int j = 1; j < n; ++j) {
82+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
83+
}
84+
}
85+
return dp[m - 1][n - 1];
86+
}
87+
}
88+
```
89+
90+
### **C++**
91+
92+
```cpp
93+
class Solution {
94+
public:
95+
int uniquePaths(int m, int n) {
96+
vector<vector<int>> dp(m, vector<int>(n, 1));
97+
for (int i = 1; i < m; ++i) {
98+
for (int j = 1; j < n; ++j) {
99+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
100+
}
101+
}
102+
return dp[m - 1][n - 1];
103+
}
104+
};
105+
```
69106
107+
### **Go**
108+
109+
```go
110+
func uniquePaths(m int, n int) int {
111+
dp := make([][]int, m)
112+
for i := 0; i < m; i++ {
113+
dp[i] = make([]int, n)
114+
}
115+
for i := 0; i < m; i++ {
116+
for j := 0; j < n; j++ {
117+
if i == 0 || j == 0 {
118+
dp[i][j] = 1
119+
} else {
120+
dp[i][j] = dp[i-1][j] + dp[i][j-1]
121+
}
122+
}
123+
}
124+
return dp[m-1][n-1]
125+
}
70126
```
71127

72128
### **...**

‎solution/0000-0099/0062.Unique Paths/Solution.cpp

Lines changed: 7 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,12 @@
11
class Solution {
22
public:
33
int uniquePaths(int m, int n) {
4-
if(m<=0||n<=0)
5-
return 0;
6-
if(m==1||n==1)
7-
return 1;
8-
int arr[m][n]={0};
9-
arr[0][0]=1;
10-
for(int i=1;i<m;i++)
11-
arr[i][0]=1;
12-
for(int j=1;j<n;j++)
13-
arr[0][j]=1;
14-
for(int i=1;i<m;i++)
15-
for(int j=1;j<n;j++)
16-
{
17-
arr[i][j]=arr[i-1][j]+arr[i][j-1];
4+
vector<vector<int>> dp(m, vector<int>(n, 1));
5+
for (int i = 1; i < m; ++i) {
6+
for (int j = 1; j < n; ++j) {
7+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
188
}
19-
return arr[m-1][n-1];
9+
}
10+
return dp[m - 1][n - 1];
2011
}
21-
};
12+
};

‎solution/0000-0099/0062.Unique Paths/Solution.go

Lines changed: 0 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,4 @@
1-
/*
2-
* 状态转移方程 dp[m][n] = dp[m-1][n] + dp[m][n-1]，初始化值 dp[m][n] = 0 (m==0 or n==0)
3-
*/
41
func uniquePaths(m int, n int) int {
5-
if m == 0 || n == 0 {
6-
return 0
7-
}
8-
if m == 1 || n == 1 {
9-
return 1
10-
}
112
dp := make([][]int, m)
123
for i := 0; i < m; i++ {
134
dp[i] = make([]int, n)

‎solution/0000-0099/0062.Unique Paths/Solution.java

Lines changed: 6 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,14 @@
11
class Solution {
22
public int uniquePaths(int m, int n) {
3-
int[][] res = new int[n][m];
3+
int[][] dp = new int[m][n];
44
for (int i = 0; i < m; ++i) {
5-
res[0][i] = 1;
5+
Arrays.fill(dp[i], 1);
66
}
7-
for (int i = 1; i < n; ++i) {
8-
res[i][0] = 1;
9-
}
10-
for (int i = 1; i < n; ++i) {
11-
for (int j = 1; j < m; ++j) {
12-
res[i][j] = res[i - 1][j] + res[i][j - 1];
7+
for (int i = 1; i < m; ++i) {
8+
for (int j = 1; j < n; ++j) {
9+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
1310
}
1411
}
15-
return res[n - 1][m - 1];
12+
return dp[m - 1][n - 1];
1613
}
1714
}

‎solution/0000-0099/0062.Unique Paths/Solution.py

Lines changed: 6 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,7 @@
11
class Solution:
2-
def uniquePaths(self, m, n):
3-
"""
4-
:type m: int
5-
:type n: int
6-
:rtype: int
7-
"""
8-
res = [[0]*m]*n
9-
for i in range(n):
10-
for j in range(m):
11-
if i == 0 or j==0:
12-
res[i][j] = 1
13-
else:
14-
res[i][j] = res[i][j-1]+res[i-1][j]
15-
return res[n-1][m-1]
2+
def uniquePaths(self, m: int, n: int) -> int:
3+
dp = [[1] * n for _ in range(m)]
4+
for i in range(1, m):
5+
for j in range(1, n):
6+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
7+
return dp[m - 1][n - 1]

‎solution/0300-0399/0304.Range Sum Query 2D - Immutable/README_EN.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515

1616
<p>&nbsp;</p>
1717
<p><strong>Example 1:</strong></p>
18-
<img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0300-0399/0304.Range%20Sum%20Query%202D%20-%20Immutable/images/sum-grid.jpg" style="width: 415px; height: 415px;" />
18+
<img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0300-0399/0304.Range%20Sum%20Query%202D%20-%20Immutable/images/304.png" style="width: 415px; height: 415px;" />
1919
<pre>
2020
<strong>Input</strong>
2121
[&quot;NumMatrix&quot;, &quot;sumRegion&quot;, &quot;sumRegion&quot;, &quot;sumRegion&quot;]

0 commit comments

Comments
 (0)