动态规划之最短路径和

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

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

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

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

示例:

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

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

动态规划(英语: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上测试,性能有待于提升,后续水平提高之后再想更优的方案吧,目前先理解解题方式。

动态规划之最短路径和

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

查看所有标签

猜你喜欢:

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

Web Caching

Web Caching

Duane Wessels / O'Reilly Media, Inc. / 2001-6 / 39.95美元

On the World Wide Web, speed and efficiency are vital. Users have little patience for slow web pages, while network administrators want to make the most of their available bandwidth. A properly design......一起来看看 《Web Caching》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

html转js在线工具
html转js在线工具

html转js在线工具