给定一个包含非负整数的 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 上测试, 性能有待于提升, 后续水平提高之后再想更优的方案吧, 目前先理解解题方式.
最后
程序的运行都是人控制的, 在程序运行之前, 确保你自己的逻辑清晰, 画图可以帮你理清逻辑.
参考
64. 最小路径和 https://leetcode-cn.com/problems/minimum-path-sum/
来源: https://juejin.im/post/5c91ffb4f265da60f206f0ba