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

Commit818f534

Browse files
author
applewjg
committed
Unique Paths I && II
Change-Id: Ibab38e244528511dc534f98c90100e88425307c5
1 parentca4eeb5 commit818f534

File tree

2 files changed

+106
-0
lines changed

2 files changed

+106
-0
lines changed

‎UniquePaths.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/*
2+
Author: King, wangjingui@outlook.com
3+
Date: Oct 9, 2014
4+
Problem: Unique Paths
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/unique-paths/
7+
Notes:
8+
A robot is located at the top-left corner of a m x n grid.
9+
The robot can only move either down or right at any point in time. The robot is trying to reach
10+
the bottom-right corner of the grid (marked 'Finish' in the diagram below).
11+
How many possible unique paths are there?
12+
13+
Solution:
14+
1. Use formula C(x,t) = t!/(x!*(t-x)!) (x should be large for calculation).
15+
2. Dynamic programming. UP(i,j) = UP(i-1,j) + UP(i,j-1).
16+
*/
17+
publicclassSolution {
18+
publicintuniquePaths_1(intm,intn) {
19+
if (m ==1 ||n ==1)return1;
20+
intt = (m-1)+(n-1);
21+
intx = (m >n) ? (m-1) : (n-1);
22+
longres =1;
23+
for (inti =t;i >x;i--)res *=i;
24+
for (inti =t-x;i >1;i--)res /=i;
25+
return (int)res;
26+
}
27+
publicintuniquePaths_2(intm,intn) {
28+
if (m ==1 ||n ==1)return1;
29+
int[][]dp =newint[m][n];
30+
for (inti =0;i <m;i++)
31+
dp[i][0] =1;
32+
for (intj =0;j <n;j++)
33+
dp[0][j] =1;
34+
for (inti =1;i <m;i++)
35+
for (intj =1;j <n;j++)
36+
dp[i][j] =dp[i-1][j] +dp[i][j-1];
37+
returndp[m-1][n-1];
38+
}
39+
publicintuniquePaths(intm,intn) {
40+
if (m ==1 ||n ==1)return1;
41+
int[]dp =newint[n];
42+
for (intj =0;j <n;j++)
43+
dp[j] =1;
44+
for (inti =1;i <m;i++)
45+
for (intj =1;j <n;j++)
46+
dp[j] =dp[j] +dp[j-1];
47+
returndp[n-1];
48+
}
49+
}

‎UniquePathsII.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
/*
2+
Author: King, higuige@gmail.com
3+
Date: Dec 25, 2014
4+
Problem: Unique Paths II
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/unique-paths-ii/
7+
Notes:
8+
Follow up for "Unique Paths":
9+
Now consider if some obstacles are added to the grids. How many unique paths would there be?
10+
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
11+
For example,
12+
There is one obstacle in the middle of a 3x3 grid as illustrated below.
13+
[
14+
[0,0,0],
15+
[0,1,0],
16+
[0,0,0]
17+
]
18+
The total number of unique paths is 2.
19+
Note: m and n will be at most 100.
20+
21+
Solution: Dynamic programming.
22+
*/
23+
24+
publicclassSolution {
25+
publicintuniquePathsWithObstacles_1(int[][]obstacleGrid) {
26+
intm =obstacleGrid.length;
27+
intn =obstacleGrid[0].length;
28+
int[][]dp =newint[m][n];
29+
if (obstacleGrid[0][0] ==1)return0;
30+
dp[0][0] =1;
31+
for (inti =1;i <m;i++)
32+
dp[i][0] =obstacleGrid[i][0] ==1 ?0 :dp[i-1][0];
33+
for (intj =1;j <n;j++)
34+
dp[0][j] =obstacleGrid[0][j] ==1 ?0 :dp[0][j-1];
35+
36+
for (inti =1;i <m;i++)
37+
for (intj =1;j <n;j++)
38+
dp[i][j] =obstacleGrid[i][j] ==1 ?0:dp[i-1][j] +dp[i][j-1];
39+
40+
returndp[m-1][n-1];
41+
}
42+
publicintuniquePathsWithObstacles_2(int[][]obstacleGrid) {
43+
intm =obstacleGrid.length;
44+
if (m ==0)return0;
45+
intn =obstacleGrid[0].length;
46+
int[]dp =newint[n];
47+
if(obstacleGrid[0][0] ==1 ||obstacleGrid[m-1][n-1] ==1)return0;
48+
dp[0] =1;
49+
for (inti =0;i <m; ++i) {
50+
dp[0] =obstacleGrid[i][0] ==1 ?0 :dp[0];
51+
for(intj =1;j <n; ++j) {
52+
dp[j] =obstacleGrid[i][j] ==1 ?0:dp[j] +dp[j-1];
53+
}
54+
}
55+
returndp[n-1];
56+
}
57+
}

0 commit comments

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