[关闭]
@Yano 2019-09-20T02:54:31.000000Z 字数 3710 阅读 1773

LeetCode 动态规划 题目分类汇总

LeetCode


公众号

coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

LeetCode解题链接

LeetCode 二叉树 题目分类汇总
干货!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,其中dp[m-1][n-1]代表从出发点(0, 0)→点(m, n)的路径个数。

优化

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

代码

利用递归,空间复杂度m * n

  1. public class Solution {
  2. public int robot(int m, int n, int[][] dp) {
  3. if(m == 0 || n == 0) {
  4. return 1;
  5. }
  6. if(dp[m][n] != -1) {
  7. return dp[m][n];
  8. }
  9. dp[m][n] = robot(m - 1, n, dp) + robot(m, n - 1, dp);
  10. return dp[m][n];
  11. }
  12. public int uniquePaths(int m, int n) {
  13. int[][] dp = new int[m][n];
  14. for(int i = 0; i < m; i++) {
  15. for(int j = 0; j < n; j++) {
  16. dp[i][j] = -1;
  17. }
  18. }
  19. return robot(m - 1, n - 1, dp);
  20. }
  21. }

迭代,空间复杂度m * n

  1. public int uniquePaths(int m, int n) {
  2. int[][] grid = new int[m][n];
  3. for(int i = 0; i<m; i++){
  4. for(int j = 0; j<n; j++){
  5. if(i==0||j==0)
  6. grid[i][j] = 1;
  7. else
  8. grid[i][j] = grid[i][j-1] + grid[i-1][j];
  9. }
  10. }
  11. return grid[m-1][n-1];
  12. }

进一步优化,空间复杂度m

  1. public class Solution {
  2. public int uniquePaths(int m, int n) {
  3. int[] dp = new int[n];
  4. for(int i = 0; i < m; i++) {
  5. for(int j = 0; j < n; j++) {
  6. if(i == 0 || j == 0)
  7. dp[j] = 1;
  8. else if(j > 0)
  9. dp[j] += dp[j - 1];
  10. }
  11. }
  12. return dp[n - 1];
  13. }
  14. }

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就好了。

代码

  1. public class Solution {
  2. public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3. int width = obstacleGrid[0].length;
  4. int[] dp = new int[width];
  5. dp[0] = 1;
  6. for(int[] row : obstacleGrid) {
  7. for(int j = 0; j < width; j++) {
  8. if(row[j] == 1)
  9. dp[j] = 0;
  10. else if(j > 0)
  11. dp[j] += dp[j - 1];
  12. }
  13. }
  14. return dp[width - 1];
  15. }
  16. }

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[m][n],表示从(0, 0)到(m - 1, n - 1)的最小的和。所以可以得出公式:

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

代码

  1. public class Solution {
  2. public int minPathSum(int[][] grid) {
  3. int m = grid.length;
  4. int n = grid[0].length;
  5. int[][] sum = new int[m][n];
  6. sum[0][0] = grid[0][0];
  7. for(int i = 1; i < m; i++) {
  8. sum[i][0] += sum[i - 1][0] + grid[i][0];
  9. }
  10. for(int j = 1; j < n; j++) {
  11. sum[0][j] += sum[0][j - 1] + grid[0][j];
  12. }
  13. for(int i = 1; i < m; i++) {
  14. for(int j = 1; j < n; j++) {
  15. sum[i][j] += Math.min(sum[i - 1][j], sum[i][j - 1]) + grid[i][j];
  16. }
  17. }
  18. return sum[m - 1][n - 1];
  19. }
  20. }

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],其中sum[i]表示包括nums[i]的,nums数组从0~i的最大连续和。

以题干中的数组[-2,1,-3,4,-1,2,1,-5,4]为例,sum数组为:

[-2, 1, -2, 4, 3, 5, 6, 1, 5]

优化

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

代码

  1. public class Solution {
  2. public int maxSubArray(int[] nums) {
  3. if(nums.length == 0) return 0;
  4. int sum = nums[0], max = nums[0];
  5. for(int i = 1; i < nums.length; i++) {
  6. sum = Math.max(nums[i], sum + nums[i]);
  7. max = Math.max(sum, max);
  8. }
  9. return max;
  10. }
  11. }

总结

对于动态规划的题目,最重要的一步就是写明递推公式初始公式,缓存计算的中间结果,以获取效率。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注