LeetCode 动态规划 题目分类汇总
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.
思路
定义一个 m * n 的矩阵 dp，其中dpm-1代表从出发点(0, 0)→点(m, n)的路径个数。
- dpi = 1 (i∈[0, m))
- dp0 = 1 (j∈[0, n))
- dpm = dpm + dpm-1 (m > 0, n > 0)
优化
- 在使用递归计算时，如果dpm计算过，就应该直接取出结果，而不是再次计算。实际中，可以将dp二维数组的初始值设置为-1，如果递归过程中，dpm!=-1，则表示计算过对应点的路径个数，直接返回结果。
- 既然每一行，计算一次就没有用了，那么是否可以将空间复杂度降低？定义dpm的空间复杂度是
m * n，如果只定义一个dpm，则可以将空间复杂度降低至m。
代码
利用递归，空间复杂度m * n：
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);
}
}迭代，空间复杂度m * n：
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];
}进一步优化，空间复杂度m：
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
Follow up for "Unique Paths":
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.
思路
和上一题很像，只不过增加了一个限制条件：有些点可能不能走。不能走的点，dp变成0就好了。
代码
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.
思路
定义一个二维数组summ，表示从(0, 0)到(m - 1, n - 1)的最小的和。所以可以得出公式：
- sum0 =
grid[0][0] + grid[0][4] ... + grid[0][n] - summ =
grid[0][0] + grid[1][0] ... + grid[m][0] - summ = min(summ - 1, summ) + gridm
summ - 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.
思路
设数组sumi，其中sumi表示包括numsi的，nums数组从0~i的最大连续和。
- sumi = max(numsi, sumi - 1 + numsi)
- max = max(sumi, max)
以题干中的数组-2,1,-3,4,-1,2,1,-5,4为例，sum数组为：
[-2, 1, -2, 4, 3, 5, 6, 1, 5]优化
sumi中的每一个数，都只会用到一次。所以可以将sumi数组，变成1个变量sum即可，sum的含义与sumi相同。
代码
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;
}
}总结
对于动态规划的题目，最重要的一步就是写明递推公式和初始公式，缓存计算的中间结果，以获取效率。