三刷 06/2022
Version #1 2 Dimensional DP - not optimal
Time O(MN)
Space O(N)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.
Memory Usage: 40.9 MB, less than 51.81% of Java online submissions for Unique Paths.
class Solution {
public int uniquePaths(int m, int n) {
// standing at one grid, it's answer would be the sum of (x - 1, y) and (x, y - 1)
// m - number of rows, n - number of colums
int[][] dp = new int[2][n];
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
if (x == 0 && y == 0) {
dp[y][x] = 1;
} else if (y == 0) {
dp[y][x] = dp[y][x - 1];
} else if (x == 0) {
dp[y % 2][x] = dp[(y - 1) % 2][x];
} else {
dp[y % 2][x] = dp[(y - 1) % 2][x] + dp[y % 2][x - 1];
}
}
}
return dp[(m - 1) % 2][n - 1];
}
}
Version #2 1D DP
Time O(MN)
Space O(N)
class Solution {
public int uniquePaths(int m, int n) {
// standing at one grid, it's answer would be the sum of (x - 1, y) and (x, y - 1)
// m - number of rows, n - number of colums
int[] dp = new int[n];
for (int y = 0; y < m; y++) {
for (int x = 0; x < n; x++) {
if (x == 0 && y == 0) {
dp[x] = 1;
} else if (y == 0) {
dp[x] = dp[x - 1];
} else if (x == 0) {
continue;
} else {
dp[x] = dp[x] + dp[x - 1];
}
}
}
return dp[n - 1];
}
}
去掉了初始化的步骤
dp[0] 永远是1
100.00 %
class Solution {
public int uniquePaths(int m, int n) {
// m -> cols, n -> rows
// dp[y][x] -> count of paths to get to y,x
// dp[y][x] = (y == 0 ? dp[y][x - 1] : dp[y - 1][x]) + (x == 0 ? dp[y - 1][x] : dp[y][x - 1];
int[] dp = new int[m];
Arrays.fill(dp, 1);
for (int y = 1; y < n; y++) {
// dp[0] = 1
for (int x = 1; x < m; x++) {
dp[x] = dp[x] + dp[x - 1];
}
}
return dp[m - 1];
}
}
一刷
public class Solution {
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
public int uniquePaths(int m, int n) {
// write your code here
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 1; i < m; i++) dp[i][0] = 1;
for (int j = 1; j < n; j++) dp[0][j] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
No comments:
Post a Comment