# 62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

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).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

## 思路

• dp[i][0] = 1 (i∈[0, m))
• dp[0][j] = 1 (j∈[0, n))
• dp[m][n] = dp[m][n-1] + dp[m-1][n] (m > 0, n > 0)

## 优化

1. 在使用递归计算时，如果dp[m][n]计算过，就应该直接取出结果，而不是再次计算。实际中，可以将dp二维数组的初始值设置为-1，如果递归过程中，dp[m][n]!=-1，则表示计算过对应点的路径个数，直接返回结果。
2. 既然每一行，计算一次就没有用了，那么是否可以将空间复杂度降低？定义dp[m][n]的空间复杂度是`m * n`，如果只定义一个dp[m]，则可以将空间复杂度降低至`m`

## 代码

```public class Solution {

public int robot(int m, int n, int[][] dp) {
if(m == 0 || n == 0) {
return 1;
}

if(dp[m][n] != -1) {
return dp[m][n];
}

dp[m][n] = robot(m - 1, n, dp) + robot(m, n - 1, dp);
return dp[m][n];
}

public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
dp[i][j] = -1;
}
}
return robot(m - 1, n - 1, dp);
}
}```

```public int uniquePaths(int m, int n) {
int[][] grid = new int[m][n];
for(int i = 0; i<m; i++){
for(int j = 0; j<n; j++){
if(i==0||j==0)
grid[i][j] = 1;
else
grid[i][j] = grid[i][j-1] + grid[i-1][j];
}
}
return grid[m-1][n-1];
}```

```public class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(i == 0 || j == 0)
dp[j] = 1;
else if(j > 0)
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}```

# 63. Unique Paths II

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example, There is one obstacle in the middle of a 3x3 grid as illustrated below.

```[
[0,0,0],
[0,1,0],
[0,0,0]
]```

The total number of unique paths is 2.

Note: m and n will be at most 100.

## 代码

```public class Solution {

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int width = obstacleGrid[0].length;
int[] dp = new int[width];
dp[0] = 1;
for(int[] row : obstacleGrid) {
for(int j = 0; j < width; j++) {
if(row[j] == 1)
dp[j] = 0;
else if(j > 0)
dp[j] += dp[j - 1];
}
}
return dp[width - 1];
}
}```

# 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

## 思路

• sum[0][n] = `grid[0][0] + grid[0][4] ... + grid[0][n]`
• sum[m][0] = `grid[0][0] + grid[1][0] ... + grid[m][0]`
• sum[m][n] = min(sum[m - 1][n], sum[m][n - 1]) + grid[m][n]

sum[m - 1][n - 1] 即为最终结果。

## 代码

```public class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] sum = new int[m][n];
sum[0][0] = grid[0][0];
for(int i = 1; i < m; i++) {
sum[i][0] += sum[i - 1][0] + grid[i][0];
}
for(int j = 1; j < n; j++) {
sum[0][j] += sum[0][j - 1] + grid[0][j];
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
sum[i][j] += Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
}
}
return sum[m - 1][n - 1];
}
}```

# 53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

## 思路

• sum[i] = max(nums[i], sum[i - 1] + nums[i])
• max = max(sum[i], max)

`[-2, 1, -2, 4, 3, 5, 6, 1, 5]`
• 当i=0时，sum[0] = -2
• 当i=1时，sum1 = max(nums1, sum[0] + nums1) = max(1, -2 + 1) = 1
• ……

## 优化

sum[i]中的每一个数，都只会用到一次。所以可以将sum[i]数组，变成1个变量sum即可，sum的含义与sum[i]相同。

## 代码

```public class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0) return 0;
int sum = nums[0], max = nums[0];
for(int i = 1; i < nums.length; i++) {
sum = Math.max(nums[i], sum + nums[i]);
max = Math.max(sum, max);
}
return max;
}
}```

# 总结

88 篇文章15 人订阅

0 条评论

## 相关文章

55350

### Leetcode 81 Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed...

20590

### Tensorflow|通过Variable及assign()感悟一点设计之道

01 Variable a = tf.Variable(2, name="scalar") # create variable a with scalar v...

2.1K70

45330

43090

35540

### Python实现随机生成验证码？小菜一碟！

Python随机生成验证码的方法有很多，今天给大家列举两种，大家也可以在这个基础上进行改造，设计出适合自己的验证码方法

15820

16810

### BZOJ4810: [Ynoi2017]由乃的玉米田(莫队+bitset)

Description 由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。 由乃认为玉米田不美，所以她决定出...

33780

29320