动态规划-路径问题

这篇具有很好参考价值的文章主要介绍了动态规划-路径问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


1. 不同路径(62)

题目描述:
动态规划-路径问题,动态规划,算法,leetcode
状态表示:
设dp[i][j]表示到达(i,j)位置时的路径数目。
状态转移方程:
dp[i][j]=dp[i-1][j]+dp[i][j-1]。这里分析起来很简单,因为这算是很经典的问题了。机器人只能向下或者向右走,所以到达(i,j)就有两种方式,分别是从(i-1,j)向下以及(i,j-1)向右,那么到达(i,j)位置的路径数只需要将到达(i-1,j)以及(i,j-1)位置的路径数相加即可。
初始化:
初始化就是为了避免越界问题,因为这里的状态转移方程涉及到i-1以及j-1。这里可以在矩阵外添加一行和一列,至于对于一行和一列的初始化要注意不能影响最终输出的结果,另外这样初始化还要注意下标的映射关系,这东西讲不清具体得看代码,这样初始化的好处就是可以将一整个矩阵全写进循环。
填表顺序:
从上到下,从左至右。
返回值:
因为添加了一行一列所以返回dp[m][n]。
代码如下:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {

            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m][n];


    }
}

题目链接
时间复杂度:O(n^2)
空间复杂度:O(n^2)

2. 不同路径 II(63)

题目描述:
动态规划-路径问题,动态规划,算法,leetcode
状态表示:
和上一题一样(i,j)位置的路径数为dp[i][j]。
状态转移方程:
实际上这题的状态转移方程也非常类似于上一题,但是要考虑一个特殊情况,就是障碍的情况。当(i,j)是障碍物的情况下直接将dp[i][j]=0,当(i,j)不是障碍物的情况下dp[i][j]=dp[i-1][j]+dp[i][j-1]。
初始化:
这里的初始化和上一题是一致的额,没什么好说的。。但是要提前判断左上角为障碍物的情况,直接返回0。
填表顺序:
从上往下,从左至右。
返回值:
与上题一致也是返回dp[m][n]。
代码如下:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m + 1][n + 1];

        dp[0][1] = 1;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }

        return dp[m][n];

    }
}

题目链接
时间复杂度:O(n^2)
空间复杂度:O(n^2)

3. 珠宝的最高价值(LCR 166)

题目描述:
动态规划-路径问题,动态规划,算法,leetcode
状态表示:
这题与上面两题也是相似的,只不过给出的矩阵多出了一个值的属性,说白了这篇博客就是将路径问题进行的一个分类总结。这题的状态表示根据经验和题目要求可以设置为dp[i][j]表示在(i,j)位置能够拿到的最大珠宝价值。
状态转移方程:
到达(i,j)位置还是只能够从(i-1,j)以及(i,j-1),因此要得到(i,j)位置的最大价值首先要将dp[i-1][j]与dp[i][j-1]的价值进行比较得到最大值赋给dp[i][j],状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]。
初始化:
还是类似加上一行和一列,但是这里不用做别的操作了,行和列赋0即可。但是还要注意dp数组与frame数组的映射关系。
填表顺序:
从上到下,从左至右。
返回值:
dp[m][n]。
代码如下:

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
}

题目链接
时间复杂度:O(n^2)
空间复杂度:O(n^2)

4. 下降路径最小和(931)

题目描述:
动态规划-路径问题,动态规划,算法,leetcode
状态表示:
根据经验加题目要求可以将dp[i][j]定义为到达(i,j)位置的最小路径和。
状态转移方程:
(i,j)上一行相邻的位置有(i-1,j)(i-1,j-1)(i-1,j+1),因此要求得到达(i,j)位置的最小路径和就可以列出以下状态转移方程,dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+ matrix[i][j]。
初始化:
要避免到达(i,j)位置的前三个位置越界可以在矩阵上加上左右两边的两列以及上边的一行,从而方便后续的操作,这里为了避免加上的空间影响最终得到的结果要注意把加上的一行赋值为0,加上的两列赋值为无穷大。
填表顺序:
从上到下,从左至右。
返回值:
要返回矩阵最后一行的最小值。
代码如下:

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dp = new int[m + 1][n + 2];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }

        for (int i = 0; i <= m; i++) {
            dp[i][n + 1] = Integer.MAX_VALUE;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            if (min > dp[m][i]) {
                min = dp[m][i];
            }
        }

        return min;
    }
}

题目链接
时间复杂度:O(n^2)
空间复杂度:O(n^2)

5. 最小路径和(64)

题目描述:
动态规划-路径问题,动态规划,算法,leetcode
状态表示:
经验加题目要求,设定dp[i][j]表示到达(i,j)位置的最小路径和。
状态转移方程:
因为只能向下以及向右移动,所以dp[i][j]的值关联于dp[i-1][j]以及dp[i][j-1],即dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j]。
初始化:
也是一样为了避免越界,要给dp加上一行和一列的空间,这里要考虑到不能影响到最终的结果,因此除了左上角的左边和上边的空间其余空间都赋为无穷大。
填表顺序:
从上到下,从左至右。
返回值:
因为增加了一行和一列,所以应该返回dp[m][n]。
代码如下:

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        dp[0][1] = 0;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }

        return dp[m][n];
    }
}

题目链接
时间复杂度:O(n^2)
空间复杂度:O(n^2)

6. 地下城游戏(174)

题目描述:
动态规划-路径问题,动态规划,算法,leetcode
状态表示:
根据经验以及题目要求这题定义dp[i][j]为以(i,j)为起点到达终点所需的最小点数。
状态转移方程:
根据经验与题目要求dp[i][j]定义为以位置(i,j)为起点营救公主所需的最低血量。因此位置(i,j)和其下边以及右边的dp元素的关系如下:
dp[i][j]+dungeon[i][j]>=dp[i+1][j]。
dp[i][j]+dungeon[i][j]>=dp[i][j+1]。
要满足以上条件,皆取最小值,即dp[i][j]=min(dp[i+1][j]-dungeon[i][j],dp[i][j+1]-dungeon[i][j]),不过要注意一个问题,当dungeon[i][j]的值是一个很大的值即一个很大的血包的时候,dp[i][j]就为负值了,要避免这种情况,如果出现血包很大的情况就将dp[i][j]直接赋为1即可,因为1就是逻辑上合理的最低血量。
初始化:
为了避免越界也要在dp上再多加一行和一列,这里的行和列是加在最后一行和最后一列。为了使添加之后不影响输出的结果,所以在行和列的每一个空间赋无穷大,只有右下角公主所在的位置的右边和下边赋为1,因为在逻辑上当营救完公主之后血量至少为1。
填表顺序:
从下到上,从右至左。
返回值:
dp[0][0]。
代码如下:

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }

        for (int i = 0; i <= n; i++) {
            dp[m][i] = Integer.MAX_VALUE;
        }

        dp[m][n - 1] = 1;
        dp[m - 1][n] = 1;

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }

        return dp[0][0];

    }
}

题目链接
时间复杂度:O(n^2)
空间复杂度:O(n^2)文章来源地址https://www.toymoban.com/news/detail-853881.html

到了这里,关于动态规划-路径问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法沉淀 —— 动态规划篇(路径问题)

    几乎所有的动态规划问题大致可分为以下5个步骤,后续所有问题分析都将基于此 1.、状态表示:通常状态表示分为基本分为以下两种,其中更是以第一种为甚。 以i为结尾 ,dp[i] 表示什么,通常为代求问题(具体依题目而定) 以i为开始 ,dp[i]表示什么,通常为代求问题(具

    2024年04月17日
    浏览(44)
  • C++算法 —— 动态规划(2)路径问题

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月06日
    浏览(50)
  • 【算法优选】 动态规划之路径问题——贰

    动态规划相关题目都可以参考以下五个步骤进行解答: 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的

    2024年02月05日
    浏览(49)
  • 【算法】动态规划中的路径问题

    君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,如果给算法的难度和复杂度排一个排名,那么动态规划算法一定名列前茅。今天,我们通过由简单到困难的两道题目带大家学会动态规划中的路径问题 好了废话不多说,开始我

    2024年02月05日
    浏览(38)
  • 基础算法之——【动态规划之路径问题】1

    今天更新动态规划路径问题1,后续会继续更新其他有关动态规划的问题!动态规划的路径问题,顾名思义,就是和路径相关的问题。当然,我们是从最简单的找路径开始! 动态规划的使用方法: 1.确定状态并定义状态数组:(i,j)代表什么意思?dp[i][j]又是什么意思? 2.确

    2024年02月07日
    浏览(41)
  • 动态规划 Leetcode 62 不同路径

    Leetcode 62 学习记录自代码随想录 要点:1.二维表格,想到(i,j)去代表其坐标,dp数组也因此为二维数组; 2.递推公式 d p [ i ] [ j ] dp[i][j] d p [ i ] [ j ] 的上一步只能是其左边或上边,所以 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[i][j-1] d p [ i ] [ j ] =

    2024年03月13日
    浏览(43)
  • 【手撕算法|动态规划系列No.2】leetcode面试题 08.01. 三步问题

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月12日
    浏览(64)
  • leetcode63. 不同路径 II(动态规划-java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/unique-paths-ii 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。 现在考虑网格中有障碍物。

    2024年02月11日
    浏览(50)
  • LeetCode刷题笔记【30】:动态规划专题-2(不同路径、不同路径 II)

    参考前文 参考文章: LeetCode刷题笔记【29】:动态规划专题-1(斐波那契数、爬楼梯、使用最小花费爬楼梯) LeetCode链接:https://leetcode.cn/problems/unique-paths/description/ 动态规划 : 创建m×n的数组, 对应这个地图, 数组 val 表示 有几种方法可以走到这一格 最开始, 第一行和第一列v

    2024年02月09日
    浏览(60)
  • 【LeetCode:64. 最小路径和 | 暴力递归=>记忆化搜索=>动态规划 】

    🚀 算法题 🚀 🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀 🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨ 🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文

    2024年02月05日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包