动态规划之最短路径和

栏目: 编程工具 · 发布时间: 5年前

内容简介:给定一个包含非负整数的**说明:**每次只能向下或者向右移动一步。昨天做了道算法题,感觉画图很有助于自己理解算法的过程,这次再挑一个算法加深印象。碰到这种类型的题目,和递归很像,但是使用递归,如果数据范围比较大,就会花费很长时间。

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

**说明:**每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
复制代码

昨天做了道算法题,感觉画图很有助于自己理解算法的过程,这次再挑一个算法加深印象。碰到这种类型的题目,和递归很像,但是使用递归,如果数据范围比较大,就会花费很长时间。

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划 常常适用于有重叠子问题和最优子结构性质的问题, 动态规划 方法所耗时间往往远少于朴素解法。

废话少说

解题

根据题意,到达网格中的某个点最短,可以理解为网格中的任何一个点都是可以走过去的,而且任何一个网格都有一个最短的路径。

那么我们使用一种数据结构保存,从顶点到达网格中任意一点的最短位置。根据人的正常逻辑,画图如下:

  • 从顶点按照行来遍历每一个位置,计算每一个位置的最小路径
动态规划之最短路径和

根据上面的图片可以了解:

点
点
点
点

至此,我们写程序如下:

public static int minPathSumAi(int[][] grid){
        // 特殊情况处理
        if (grid.length == 0){
            return 0;
        }

        // 新建一个标记数组,标记到每个位置的最短路径
        int xLen = grid.length;
        int yLen = grid[0].length;
        int[][] markBit = new int[xLen][yLen];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                // 初始位置
                if (i == 0 && j == 0){
                    markBit[i][j] = grid[i][j];
                }
                // 当点在第一行的位置时
                else if (i == 0){
                    markBit[i][j] = markBit[i][j-1] + grid[i][j];
                }
                // 当点在第一列的位置时
                else if (j == 0){
                    markBit[i][j] = markBit[i-1][j] + grid[i][j];
                }
                // 当点在数组的中间位置时
                else {
                    markBit[i][j] = Math.min(markBit[i-1][j] , markBit[i][j-1]) + grid[i][j];
                }
            }
        }

        return markBit[xLen-1][yLen-1];
    }
复制代码

然后到LeetCode上测试,性能有待于提升,后续水平提高之后再想更优的方案吧,目前先理解解题方式。

动态规划之最短路径和

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

部落:一呼百应的力量

部落:一呼百应的力量

高汀 (Godin.S.) / 刘晖 / 中信出版社 / 2009-7 / 26.00元

部落指的是任何一群人,规模可大可小,他们因追随领导、志同道合而相互联系在一起。人类其实数百万年前就有部落的出现,随之还形成了宗教、种族、政治或甚至音乐。 互联网消除了地理隔离,降低了沟通成本并缩短了时间。博客和社交网站都有益于现有的部落扩张,并促进了网络部落的诞生——这些部落的人数从10个到1000万个不等,他们所关注的也许是iPhone,或一场政治运动,或阻止全球变暖的新方法。 那么......一起来看看 《部落:一呼百应的力量》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具