首页 > 其他分享 >【博学谷学习记录】超强总结,用心分享 | 动态规划经典例题总结一

【博学谷学习记录】超强总结,用心分享 | 动态规划经典例题总结一

时间:2022-12-22 10:01:11浏览次数:32  
标签:总结 obstacleGrid int 机器人 路径 网格 超强 例题 dp

不同路径Ⅰ

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

解题思路

一、定义数组元素的含义

由于我们的目的是从左上角到右下角一共有多少种路径,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i] [j] 种路径。那么,dp[m-1] [n-1] 就是我们要的答案了。

注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要找的答案。

二、找出关系数组元素间的关系式

想象以下,机器人要怎么样才能到达 (i, j) 这个位置?由于机器人可以向下走或者向右走,所以有两种方式到达

一种是从 (i-1, j) 这个位置走一步到达

一种是从(i, j - 1) 这个位置走一步到达

因为是计算所有可能的步骤,所以是把所有可能走的路径都加起来,所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

三、找出初始值

显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0,那么还能使用关系式吗?答是不能的,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了,所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。这个还是非常容易计算的,相当于计算机图中的最上面一行和左边一列。因此初始值如下:

dp[0] [0….n-1] = 1; // 相当于最上面一行,机器人只能一直往左走

dp[0…m-1] [0] = 1; // 相当于最左面一列,机器人只能一直往下走


代码(java)

class Solution {
    
    public static void main(String[] args) {
        System.out.println(method(3, 7));
    }
    
    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        for (int i = 0; i < m; i++) {
            dp[i][0]=1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i]=1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                dp[i][j]= dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
}

不同路径 Ⅱ

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 10 来表示。

提示:

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j]01

解题思路

一、定义数组元素的含义

由于我们的目的是从左上角到右下角一共有多少种路径,那我们就定义 dp[i] [j]的含义为:当机器人从左上角走到(i, j) 这个位置时,一共有 dp[i] [j] 种路径。那么,dp[m-1] [n-1] 就是我们要的答案了。

注意,这个网格相当于一个二维数组,数组是从下标为 0 开始算起的,所以 右下角的位置是 (m-1, n - 1),所以 dp[m-1] [n-1] 就是我们要找的答案。

二、找出关系数组元素间的关系式

该题和不同路径 Ⅰ的关系相似。

由于机器人可以向下走或者向右走,所以有两种方式到达

一种是从 (i-1, j) 这个位置走一步到达

一种是从(i, j - 1) 这个位置走一步到达

因为是计算所有可能的步骤,所以是把所有可能走的路径都加起来,考虑网格中有障碍物,机器人无法通过障碍物,所以障碍物所在位置没有路径值。

所以关系式是 :

if (obstacleGrid[i][j] != 1){
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
三、找出初始值

显然,当 dp[i] [j] 中,如果 i 或者 j 有一个为 0时使用该关系式就不合适了,因为这个时候把 i - 1 或者 j - 1,就变成负数了,数组就会出问题了;所以我们的初始值是计算出所有的 dp[0] [0….n-1] 和所有的 dp[0….m-1] [0]。

而且还要考虑到障碍物会出现在dp[0] [0….n-1] 和dp[0….m-1] [0]之中,我们可以加一个判断语句进行赋值,或者在初始化过程中遇到障碍物后,直接结束初始化(因为只要碰到障碍物,后面的路径机器人都无法到达)。


代码

class Solution {
    public static void main(String[] args) {
        int[][] obstacleGrid=new int[][]{{0,0,0},{0,1,0},{0,0,0}};

        System.out.println(uniquePathsWithObstacles(obstacleGrid));
    }
    
    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];
        //初始化第一列
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1){
                break;
            }
            dp[i][0] = 1;
        }
        //初始化第一行
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1){
                break;
            }
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //跳过路障
                if (obstacleGrid[i][j] != 1){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
}

标签:总结,obstacleGrid,int,机器人,路径,网格,超强,例题,dp
From: https://www.cnblogs.com/Azureblue/p/16997725.html

相关文章

  • 工作5年的老程序员的年终总结
    看了上篇的博客是2020年9月10号,已经两年多没写博客了,重新执笔开始写篇年终总结!时间飞逝,已经毕业5年多,这一路经历太多了,这篇博客对整个经历进行复盘和总结。......
  • 冲刺总结(七)
    冲刺总结(七)一、登录注册这里注册用户lcy1211,密码设置为123456来到数据库,我们可以看到刚刚注册的用户lcy1211,和通过密态储存的口令123456二、加解密本项目在kali......
  • 12月21日内容总结——forms组件渲染标签、展示信息、校验数据的一些补充,forms组件参数
    目录一、forms组件渲染标签二、forms组件展示信息三、forms组件校验补充四、forms组件参数补充五、forms组件源码剖析六、modelform组件什么是modelform组件?使用校验性组件......
  • Pandas中高效的选择和替换操作总结
    使用正确的工具和技术来最大限度地利用数据是很重要的。Pandas是数据操作、分析和可视化的重要工具,有效地使用Pandas可能具有挑战性,从使用向量化操作到利用内置函数,这些最佳......
  • Express框架总结
    express框架总结Express安装通过express提供的脚手架直接创建一个应用安装脚手架:npminstall-gexpress-generator创建项目:expressexpress-demo安装依赖:npmi......
  • TI工程师总结的判断ADS129x是否工作正常的方法步骤
    当大多数ADC出现无响应时,可以通过一些基本的调试技术帮助验证器件是否仍然正常工作。以下是ADS129x器件出现无响应时需要采取的一些基本步骤:为器件通电。然后探测器......
  • 2022年总结
    转眼,2022年就剩下十多天了。 倒是应了那句老话:“人生天地之间,若白驹过隙,忽然而已。” 不管你是否准备好,2022年倒计时的钟表已经敲响,最后十天,请记得好好地谢谢自己!......
  • “互帮互助”小程序开发总结
    这次小程序开发的经历让我学到了很多,下面我就将一一总结我从中学到的知识1.我学会了规范的编程。以前的我不懂编程规范,编出来的代码既不写注释,阅读性又很差,而且变量名大部......
  • 标准 C++ 中的 string 类的用法总结
     相信使用过MFC编程的朋友对CString这个类的印象应该非常深刻吧?的确,MFC中的CString类使用起来真的非常的方便好用。但是如果离开了MFC框架,还有没有这样使用起来......
  • QCustomPlot基础教程(十三)——Qt中QCustomPlot清除已绘制的曲线方法总结(全面汇总)
    https://blog.csdn.net/didi_ya/article/details/121237553目录1、前言2、方法一——clearGraphs()3、方法二——clearPlottables()4、方法三——clear()5、方法四......