Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite091443

Browse files
author
luzhipeng
committed
1 parenta6e3a21 commite091443

File tree

8 files changed

+147
-72
lines changed

8 files changed

+147
-72
lines changed

‎62.unique-paths.js

Lines changed: 0 additions & 71 deletions
This file was deleted.

‎README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,7 +98,8 @@ leetcode 题解，记录自己的 leetcode 解题之路。
9898
-[11.container-with-most-water](./problems/11.container-with-most-water.md)
9999
-[19. Remove Nth Node From End of List](./problems/removeNthNodeFromEndofList.md)
100100
-[24. Swap Nodes In Pairs](./problems/swapNodesInPairs.md)
101-
- 🆕[55.jump-game.md](./problems/55.jump-game.md.md)
101+
- 🆕[55.jump-game.md](./problems/55.jump-game.md)
102+
- 🆕[62.unique-paths](./problems/62.unique-paths.md)
102103
-[75.sort-colors.md](./problems/75.sort-colors.md)
103104
-[86.partition-list](./problems/86.partition-list.md)
104105
-[92.reverse-linked-list-ii](./problems/92.reverse-linked-list-ii.md)
Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
<mxfile modified="2019-04-23T09:48:23.409Z" host="www.draw.io" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.86 Safari/537.36" etag="GTTmjchVZQ0qfG9G-_4Q" version="10.6.3" type="device"><diagram id="tn9JAYlXwyHzK-nR11YM" name="第 1 页">7Ztdj5s4FIZ/jS93hDGfl5Ah24tdtVIq9bJyg0NQAVNwmsz++rXBJIDJJFUTiBoy0gSOD8a8D9jn2ASgRXr4u8D59l8akgToWngA6BXoOkSuw7+E5a22OIZRG6IiDqXTybCK/yPSqEnrLg5J2XFklCYszrvGNc0ysmYdGy4Kuu+6bWjSPWuOI6IYVmucqNYvcci28ip0+2T/QOJo25wZWm5dkuLGWV5JucUh3bdMKABoUVDK6q30sCCJEK/RpT5ueab02LCCZOyaA+zP+x9W+hl9hMaHVbRcad8/5n/JWn7iZCcvWDaWvTUK8Fq42HzH329jRlY5XouSPefNbVuWJnwP8k1c5jWBTXwg/KS+rJsUjBzONhoepeD3EKEpYcUbd5EH6I5UT94+ptzdn1hY0rRtYWhsWNKPjhWfBOIbUqNf0EtX9MIPJhjsCgbRxIohRbH8sRSDZlcxXZtYMePhFdN6itkTK2YqiiUPppjVVQxN3Y9ZimLkwRTr9WOGPrFi9uWR8jjCa1yDEJdbIUa10xKrZAX9ThY0oQW3ZDQTAif4G0k+0TJmMc24ec1VIrzcFxrGPBr5p+fwjTJG05aDl8SRKGBUwMFy71gPb1ouWpkeIhGnvaTlGpOXkOQFWWNGwpecltzzaxUycf9NnCRNG4GONM1fLDktv6AMyyYg/UYjVu/ZgAP9rz5A2rwXaXcmfSfSvXEDDowbo5Ju+pgZ9a1RQ6MXIhhTo1Yj92dHfTPWvQAaaebErNWc49lZ3wu1OzVqNVmKyy+0CLkNIE/MFhU7NbTlCrBeDNun0IeVxmGYnAuGC7rLwuMdtKEZawFZLg1Pt6RdznBB+1ZDarebtVUex3hqHCBqLvbMQAx9ciBqqtcDssFJ+ScT6fVZcCAUOc6SjYNEzSWfCwlsuqnjlNvAUzIuEufZkbj9GarJkVyRh18MuVpghqOvOsRrlnb0gfArITj7muI8j7PoJd+V21Pg1cNwDlcY88hNtmxPSnYbYobdJWZdOdKgewHTr8imZ2DtgWhyYlcs/83EWuMUnJzYFdMYM7EWMXcg2BuX2BWTETOxVuAx/TimzinMxN4hZqDJiak5LlSQqaF6d3qPC2dVH3VKbWOKvxsG9/AyxPpzG2JWbzF1YN3FGOCl342XmgCrj9jM6xQpDrwuMC4wNT1GM7DzwPSBtxXGBaYmz8YM7B1gAwsZowJDavJszsDOA0NTj2FIzZ2tGdh5YENR4rjA5tT5XWD9t3PMgTeHxw3r0VDqbCVMSgPEW/+NOtaPHa2FQK4darbdNllR9R04wF8C1wWBAXwHeB4IbOAFwHsFgQk8bjSqIh94SDh7EHgOCCzgLYGzrDYWwsidnUC4cYvjAj+oDl9WFhP4r8BFlY8LnKpmHwJHr5wXwLEr5wC4njiF41VFtvjvu2KD2x1DNlU426INjt9cOBeyvnZ5TZd7nFsvSNx44QFB8+Jth5r1ot/sKPju6fcWVVnrVyso+B8=</diagram></mxfile>

‎assets/drawio/62.unique-paths.drawio

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
<mxfile modified="2019-04-23T11:42:57.322Z" host="www.draw.io" agent="Mozilla/5.0 (Macintosh; Intel Mac OS X 10_12_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.86 Safari/537.36" etag="WTlwpOlKDbydg-200h0-" version="10.6.3" type="device"><diagram id="LLvs7Lyrv3_SIfY0iaOW" name="第 1 页">7Vvfj5s4EP5r/NgIMBDzCAnpSe1Je7cPvT6dHHCIewRnwdkk99efDSb8rMrukYSqiVYKHnsG831je2bIArjYnT6meL/9nYUkBoYWngBcAsPQoYPEl5ScCwkyzUIQpTRUgyrBM/2XKKGmpAcakqwxkDMWc7pvCgOWJCTgDRlOU3ZsDtuwuHnXPY5IR/Ac4Lgr/UJDvlVPYcwr+W+ERtvyzrrtFD07XA5WT5JtcciONRH0AVykjPHiandakFiCV+JS6K2+03uZWEoSPkThj7X+khp/0tVrsHI/ul+Wnz55H5SVVxwf1AOryfJziUDKDklIpBENQO+4pZw873Ege4+CcyHb8l0sWrq43NA4XrCYpbkuDC2CQlPIM56yf0itBxlraNuiR02ApJycvvtk+gUv4WiE7QhPz2LIqekrysUMTbWPFWGWEm1rXJUyrFwkuhiuUBQXCsg3gGqMDOoIENkTgwhODyJ9am5kThCjFkTWnSGyJw8RvLcXzacP0b29CE0PovZ+fW+InMlDdPeFVnr1lDG6txvpUzzTpnao6db0Qbr/ahv76G9lLhsUkCDoy1zWyDIt7Uqw3t33BoQLl0RWghDibHuBuAZnE7aEJULZi/GaxE8so5yyRIgDARMR/Z4EkYqk+3NrwJpxzna1AW5MI9nBmaQPq9bFjpjaXs5yd4pkOWK2ywJMZiHZpyTAnISzPcvEyL/zykCXdE3zFitDPhUVCmoOCUslFdcIn8uV/gO2jWuxbQw4sh5sv5ftudVk2+5h27ol2wOKPb8Y2wRn/DpkG92N3OhZ2vBqZA+osDzIfu8+bjTZhhocxLaJrsX2gLj6wfZYbFvGfdmGE8w0odGMbXRtWGxzvQrz2K82xgBpPjWQjOmBZE7Ok3qOUh8BzwKeBnwLIJRfzIG7EH9UiZy5FDkuQCbwbYA04Hl51wq4K6mPIPCWssvJDbVhFwDyAXtzfStUos722t6FdzQM5W16yWzSvWEJVy9ldaTatZ3XmS+1+XykxaG1t9kO7Trq4d2+Gu/dQ1X/OWlaraD4jLXRN2lyujSZt8xhYbda9mBJnDQTY6lbroMPlsypraVu9a8bD5AwIs+qKYslLGIJjv1K2sKzGvOZyfA/J/Yb4fysUMYHzpq0kxPlf0n1maVaX2s9y5OynDfOZSMRCNSUZPNrs1kp5q2G5hNJqQBROs87vEBi8lYfSEmMOX1t6vVRqlSfGBUWqxXumK0wqZVuZOyQBkRpVY7xQ0NOyw7HaUR4x07uYJfH+R8+1/P2VYRJrgkcW154OkC5xPOB68qYCvkqglIRmAk8JOMrEUrJCEwH/gp4CxmDyXBLhF7WG+1YwCnUCztOI5ATcZ2XT0yMdJxyzELaEbd2UR4IClMuMOyYK88B8gdqpfPYLwdWpKZws8ndqCayo/y7jCZrs8rtixspswLswnJL45eKP7X8M1Kab7dKeD3VeVu/5XZs9mRn71garjnO0pB2prY03Mr+Y2lccWm0Xlw53XrnjZdGX04OJZWo7+LBYKvyBM3u+4kbM9jNrpdPD6IuZawyrOt5kXTTnMDs5te2MTsk9OVAPuwx32YDSLulp7erhx349L7qofl2/ESz+vV+EQ5X/wMB/f8A</diagram></mxfile>

‎assets/problems/62.unique-paths-1.png

9.46 KB
Loading

‎assets/problems/62.unique-paths-2.png

8.74 KB
Loading

‎assets/problems/62.unique-paths-3.png

51 KB
Loading

‎problems/62.unique-paths.md

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
2+
##题目地址
3+
https://leetcode.com/problems/unique-paths/description/
4+
5+
##题目描述
6+
```
7+
8+
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
9+
10+
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).
11+
12+
How many possible unique paths are there?
13+
```
14+
![62.unique-paths-1](../assets/problems/62.unique-paths-1.png)
15+
16+
```
17+
Above is a 7 x 3 grid. How many possible unique paths are there?
18+
19+
Note: m and n will be at most 100.
20+
21+
Example 1:
22+
23+
Input: m = 3, n = 2
24+
Output: 3
25+
Explanation:
26+
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
27+
1. Right -> Right -> Down
28+
2. Right -> Down -> Right
29+
3. Down -> Right -> Right
30+
Example 2:
31+
32+
Input: m = 7, n = 3
33+
Output: 28
34+
```
35+
36+
##思路
37+
这是一道典型的适合使用动态规划解决的题目，它和爬楼梯等都属于动态规划中最简单的题目，
38+
因此也经常会被用于面试之中。
39+
40+
读完题目你就能想到动态规划的话，建立模型并解决恐怕不是难事。其实我们很容易看出，由于机器人只能右移动和下移动，
41+
因此第[i, j]个格子的总数应该等于[i - 1, j] +[i, j -1]， 因为第[i,j]个格子一定是从左边或者上面移动过来的。
42+
43+
![62.unique-paths-2](../assets/problems/62.unique-paths-2.png)
44+
45+
代码大概是：
46+
47+
```js
48+
constdp= [];
49+
for (let i=0; i< m+1; i++) {
50+
dp[i]= [];
51+
dp[i][0]=0;
52+
}
53+
for (let i=0; i< n+1; i++) {
54+
dp[0][i]=0;
55+
}
56+
for (let i=1; i< m+1; i++) {
57+
for(let j=1; j< n+1; j++) {
58+
dp[i][j]= j===1?1: dp[i-1][j]+ dp[i][j-1];// 转移方程
59+
}
60+
}
61+
62+
return dp[m][n];
63+
64+
```
65+
66+
由于dp[i][j] 只依赖于左边的元素和上面的元素，因此空间复杂度可以进一步优化， 优化到O(n).
67+
68+
![62.unique-paths-3](../assets/problems/62.unique-paths-3.png)
69+
70+
具体代码请查看代码区。
71+
72+
##关键点
73+
74+
- 空间复杂度可以进一步优化到O(n), 这会是一个考点
75+
- 基本动态规划问题
76+
##代码
77+
78+
```js
79+
/*
80+
* @lc app=leetcode id=62 lang=javascript
81+
*
82+
* [62] Unique Paths
83+
*
84+
* https://leetcode.com/problems/unique-paths/description/
85+
*
86+
* algorithms
87+
* Medium (46.53%)
88+
* Total Accepted: 277K
89+
* Total Submissions: 587.7K
90+
* Testcase Example: '3\n2'
91+
*
92+
* A robot is located at the top-left corner of a m x n grid (marked 'Start' in
93+
* the diagram below).
94+
*
95+
* The robot can only move either down or right at any point in time. The robot
96+
* is trying to reach the bottom-right corner of the grid (marked 'Finish' in
97+
* the diagram below).
98+
*
99+
* How many possible unique paths are there?
100+
*
101+
*
102+
* Above is a 7 x 3 grid. How many possible unique paths are there?
103+
*
104+
* Note: m and n will be at most 100.
105+
*
106+
* Example 1:
107+
*
108+
*
109+
* Input: m = 3, n = 2
110+
* Output: 3
111+
* Explanation:
112+
* From the top-left corner, there are a total of 3 ways to reach the
113+
* bottom-right corner:
114+
* 1. Right -> Right -> Down
115+
* 2. Right -> Down -> Right
116+
* 3. Down -> Right -> Right
117+
*
118+
*
119+
* Example 2:
120+
*
121+
*
122+
* Input: m = 7, n = 3
123+
* Output: 28
124+
*
125+
* START
126+
*/
127+
/**
128+
*@param{number}m
129+
*@param{number}n
130+
*@return{number}
131+
*/
132+
varuniquePaths=function(m,n) {
133+
constdp=Array(n).fill(1);
134+
135+
for(let i=1; i< m; i++) {
136+
for(let j=1; j< n; j++) {
137+
dp[j]= dp[j]+ dp[j-1];
138+
}
139+
}
140+
141+
return dp[n-1];
142+
};
143+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp