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)的路径个数。

  • 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

代码

利用递归,空间复杂度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.

思路

定义一个二维数组sum[m][n],表示从(0, 0)到(m - 1, n - 1)的最小的和。所以可以得出公式:

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

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

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

[-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;
    }
}

总结

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小鹏的专栏

Pandas处理csv表格

可以结合这篇使用:数据处理利器Pandas使用手册 1)读取csv文件 data =pandas.read_csv(‘test.csv’) //返回的是Data...

55350
来自专栏计算机视觉与深度学习基础

Leetcode 81 Search in Rotated Sorted Array II

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

20590
来自专栏算法channel

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

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

2.1K70
来自专栏程序生活

美团NLP实习面试总结一 基本知识4 数据结构二 NLP相关技术1 LSTM2 介绍实体链接与实体映射3 解释随机游走的原理及作用4 命名实体识别

机会总是留给有准备的人 一 基本知识 1 python 解释下装饰器和生成器的作用以及用法 类的知识点,类与对象,三个输出 2 java HashMap的实现原...

45330
来自专栏数据结构与算法

P1008 三连击

题目背景 本题为提交答案题,您可以写程序或手算在本机上算出答案后,直接提交答案文本,也可提交答案生成程序。 题目描述 将1,2,…,9共9个数分成三组,分别组成...

43090
来自专栏AI派

TensorFlow修炼之道(2)——变量(Variable)

变量(Variable)是 TensorFlow 中程序处理的共享持久状态的最佳方法。与常量不同的时,常量创建后,值便无法更改,但是变量创建后 可以修改。并且修...

35540
来自专栏程序员的知识天地

Python实现随机生成验证码?小菜一碟!

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

15820
来自专栏ACM算法日常

交错字符串(动态规划)- leetcode 97

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

16810
来自专栏数据结构与算法

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

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

33780
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

29320

扫码关注云+社区

领取腾讯云代金券