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

Commitd8fb657

Browse files
committed
Add Unique Paths problem with backtracking and DP solutions.
1 parent863dbdb commitd8fb657

File tree

6 files changed

+224
-0
lines changed

6 files changed

+224
-0
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -118,6 +118,7 @@ a set of rules that precisely define a sequence of operations.
118118
*`B`[Tower of Hanoi](src/algorithms/uncategorized/hanoi-tower)
119119
*`B`[Square Matrix Rotation](src/algorithms/uncategorized/square-matrix-rotation) - in-place algorithm
120120
*`B`[Jump Game](src/algorithms/uncategorized/jump-game) - backtracking, dynamic programming (top-down + bottom-up) and greedy examples
121+
*`B`[Unique Paths](src/algorithms/uncategorized/unique-paths) - backtracking and dynamic programming examples
121122
*`A`[N-Queens Problem](src/algorithms/uncategorized/n-queens)
122123
*`A`[Knight's Tour](src/algorithms/uncategorized/knight-tour)
123124

@@ -151,6 +152,7 @@ algorithm is an abstraction higher than a computer program.
151152
***Dynamic Programming** - build up a solution using previously found sub-solutions
152153
*`B`[Fibonacci Number](src/algorithms/math/fibonacci)
153154
*`B`[Jump Game](src/algorithms/uncategorized/jump-game)
155+
*`B`[Unique Paths](src/algorithms/uncategorized/unique-paths)
154156
*`A`[Levenshtein Distance](src/algorithms/string/levenshtein-distance) - minimum edit distance between two sequences
155157
*`A`[Longest Common Subsequence](src/algorithms/sets/longest-common-subsequence) (LCS)
156158
*`A`[Longest Common Substring](src/algorithms/string/longest-common-substring)
@@ -166,6 +168,7 @@ algorithm is an abstraction higher than a computer program.
166168
if it satisfies all conditions, and only then continue generating subsequent solutions. Otherwise, backtrack, and go on a
167169
different path of finding a solution. Normally the DFS traversal of state-space is being used.
168170
*`B`[Jump Game](src/algorithms/uncategorized/jump-game)
171+
*`B`[Unique Paths](src/algorithms/uncategorized/unique-paths)
169172
*`A`[Hamiltonian Cycle](src/algorithms/graph/hamiltonian-cycle) - Visit every vertex exactly once
170173
*`A`[N-Queens Problem](src/algorithms/uncategorized/n-queens)
171174
*`A`[Knight's Tour](src/algorithms/uncategorized/knight-tour)
Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
#Unique Paths Problem
2+
3+
A robot is located at the top-left corner of a`m x n` grid
4+
(marked 'Start' in the diagram below).
5+
6+
The robot can only move either down or right at any point in
7+
time. The robot is trying to reach the bottom-right corner
8+
of the grid (marked 'Finish' in the diagram below).
9+
10+
How many possible unique paths are there?
11+
12+
![Unique Paths](https://leetcode.com/static/images/problemset/robot_maze.png)
13+
14+
##Examples
15+
16+
**Example#1**
17+
18+
```
19+
Input: m = 3, n = 2
20+
Output: 3
21+
Explanation:
22+
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
23+
1. Right -> Right -> Down
24+
2. Right -> Down -> Right
25+
3. Down -> Right -> Right
26+
```
27+
28+
**Example#2**
29+
30+
```
31+
Input: m = 7, n = 3
32+
Output: 28
33+
```
34+
35+
##Algorithms
36+
37+
###Backtracking
38+
39+
First thought that might came to mind is that we need to build a decision tree
40+
where`D` means moving down and`R` means moving right. For example in case
41+
of boars`width = 3` and`height = 2` we will have the following decision tree:
42+
43+
```
44+
START
45+
/ \
46+
D R
47+
/ / \
48+
R D R
49+
/ / \
50+
R R D
51+
52+
END END END
53+
```
54+
55+
We can see three unique branches here that is the answer to our problem.
56+
57+
**Time Complexity**:`O(2 ^ n)` - roughly in worst case with square board
58+
of size`n`.
59+
60+
**Auxiliary Space Complexity**:`O(m + n)` - since we need to store current path with
61+
positions.
62+
63+
###Dynamic Programming
64+
65+
Let's treat`BOARD[i][j]` as our sub-problem.
66+
67+
Since we have restriction of moving only to the right
68+
and down we might say that number of unique paths to the current
69+
cell is a sum of numbers of unique paths to the cell above the
70+
current one and to the cell to the left of current one.
71+
72+
```
73+
BOARD[i][j] = BOARD[i - 1][j] + BOARD[i][j - 1]; // since we can only move down or right.
74+
```
75+
76+
Base cases are:
77+
78+
```
79+
BOARD[0][any] = 1; // only one way to reach any top slot.
80+
BOARD[any][0] = 1; // only one way to reach any slot in the leftmost column.
81+
```
82+
83+
For the board`3 x 2` our dynamic programming matrix will look like:
84+
85+
|| 0| 1| 1|
86+
|:---:|:---:|:---:|:---:|
87+
|**0**| 0| 1| 1|
88+
|**1**| 1| 2| 3|
89+
90+
Each cell contains the number of unique paths to it. We need
91+
the bottom right one with number`3`.
92+
93+
**Time Complexity**:`O(m * n)` - since we're going through each cell of the DP matrix.
94+
95+
**Auxiliary Space Complexity**:`O(m * n)` - since we need to have DP matrix.
96+
97+
##References
98+
99+
-[LeetCode](https://leetcode.com/problems/unique-paths/description/)
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
importbtUniquePathsfrom'../btUniquePaths';
2+
3+
describe('btUniquePaths',()=>{
4+
it('should find the number of unique paths on board',()=>{
5+
expect(btUniquePaths(3,2)).toBe(3);
6+
expect(btUniquePaths(7,3)).toBe(28);
7+
expect(btUniquePaths(3,7)).toBe(28);
8+
expect(btUniquePaths(10,10)).toBe(48620);
9+
expect(btUniquePaths(100,1)).toBe(1);
10+
expect(btUniquePaths(1,100)).toBe(1);
11+
});
12+
});
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
importdpUniquePathsfrom'../dpUniquePaths';
2+
3+
describe('dpUniquePaths',()=>{
4+
it('should find the number of unique paths on board',()=>{
5+
expect(dpUniquePaths(3,2)).toBe(3);
6+
expect(dpUniquePaths(7,3)).toBe(28);
7+
expect(dpUniquePaths(3,7)).toBe(28);
8+
expect(dpUniquePaths(10,10)).toBe(48620);
9+
expect(dpUniquePaths(100,1)).toBe(1);
10+
expect(dpUniquePaths(1,100)).toBe(1);
11+
});
12+
});
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
/**
2+
* BACKTRACKING approach of solving Unique Paths problem.
3+
*
4+
*@param {number} width - Width of the board.
5+
*@param {number} height - Height of the board.
6+
*@param {number[][]} steps - The steps that have been already made.
7+
*@param {number} uniqueSteps - Total number of unique steps.
8+
*@return {number} - Number of unique paths.
9+
*/
10+
exportdefaultfunctionbtUniquePaths(width,height,steps=[[0,0]],uniqueSteps=0){
11+
// Fetch current position on board.
12+
constcurrentPos=steps[steps.length-1];
13+
14+
// Check if we've reached the end.
15+
if(currentPos[0]===width-1&&currentPos[1]===height-1){
16+
// In case if we've reached the end let's increase total
17+
// number of unique steps.
18+
returnuniqueSteps+1;
19+
}
20+
21+
// Let's calculate how many unique path we will have
22+
// by going right and by going down.
23+
letrightUniqueSteps=0;
24+
letdownUniqueSteps=0;
25+
26+
// Do right step if possible.
27+
if(currentPos[0]<width-1){
28+
steps.push([
29+
currentPos[0]+1,
30+
currentPos[1],
31+
]);
32+
33+
// Calculate how many unique paths we'll get by moving right.
34+
rightUniqueSteps=btUniquePaths(width,height,steps,uniqueSteps);
35+
36+
// BACKTRACK and try another move.
37+
steps.pop();
38+
}
39+
40+
// Do down step if possible.
41+
if(currentPos[1]<height-1){
42+
steps.push([
43+
currentPos[0],
44+
currentPos[1]+1,
45+
]);
46+
47+
// Calculate how many unique paths we'll get by moving down.
48+
downUniqueSteps=btUniquePaths(width,height,steps,uniqueSteps);
49+
50+
// BACKTRACK and try another move.
51+
steps.pop();
52+
}
53+
54+
// Total amount of unique steps will be equal to total amount of
55+
// unique steps by going right plus total amount of unique steps
56+
// by going down.
57+
returnrightUniqueSteps+downUniqueSteps;
58+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/**
2+
* DYNAMIC PROGRAMMING approach of solving Unique Paths problem.
3+
*
4+
*@param {number} width - Width of the board.
5+
*@param {number} height - Height of the board.
6+
*@return {number} - Number of unique paths.
7+
*/
8+
exportdefaultfunctiondpUniquePaths(width,height){
9+
// Init board.
10+
constboard=Array(height).fill(null).map(()=>{
11+
returnArray(width).fill(0);
12+
});
13+
14+
// Base case.
15+
// There is only one way of getting to board[0][any] and
16+
// there is also only one way of getting to board[any][0].
17+
// This is because we have a restriction of moving right
18+
// and down only.
19+
for(letrowIndex=0;rowIndex<height;rowIndex+=1){
20+
for(letcolumnIndex=0;columnIndex<width;columnIndex+=1){
21+
if(rowIndex===0||columnIndex===0){
22+
board[rowIndex][columnIndex]=1;
23+
}
24+
}
25+
}
26+
27+
// Now, since we have this restriction of moving only to the right
28+
// and down we might say that number of unique paths to the current
29+
// cell is a sum of numbers of unique paths to the cell above the
30+
// current one and to the cell to the left of current one.
31+
for(letrowIndex=1;rowIndex<height;rowIndex+=1){
32+
for(letcolumnIndex=1;columnIndex<width;columnIndex+=1){
33+
constuniquesFromTop=board[rowIndex-1][columnIndex];
34+
constuniquesFromLeft=board[rowIndex][columnIndex-1];
35+
board[rowIndex][columnIndex]=uniquesFromTop+uniquesFromLeft;
36+
}
37+
}
38+
39+
returnboard[height-1][width-1];
40+
}

0 commit comments

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