找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

编程算法题:最小路径和(动态规划)

admin 2019-10-9 09:07 96人围观 C++相关




是新朋友吗?记得先点蓝字关注我哦~


题目描述

给定一个包含非负整数的m x n网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。说明:每次只能向下或者向右移动一步。示例:输入:[  [1,3,1], [1,5,1], [4,2,1]]输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。

解决思路

这道题主要用到思路是:动态规划。确定状态:m*n的最小路径可以看成m-1*n-1的最小路径,m-1*n-1的到m*n有两种可能,向下或者向右,由此我们可以得出转移方程:f(m,n)=min(f(m,n-1)+grid(m,n),f(m-1,n)+grid(m,n))。初始条件:m=0的时候,只能向右走,即f(m,n)=f(0,n-1)+grid(m,n);n=0的时候,只能向下走,即f(m,n)=f(m-1,0)+grid(m,n)。

Java代码实现

    publicclassSolution {publicintminPathSum(int[][] grid) {if (null == grid) {return0; }
    int row= grid.length;int col = grid[row - 1].length;
    int result[][] = newint[row][col];for (int i = 0; i < row; i++){for (int j = 0; j < col; j++) {if (i== 0) {if (j == 0) { result[i][j] =grid[0][0]; } else { result[i][j] =result[i][j - 1] + grid[i][j]; } } elseif (j == 0) {if (i== 0) { result[i][j] =grid[0][0]; } else { result[i][j] =result[i - 1][j] + grid[i][j]; } } else { result[i][j] = Math.min(result[i][j- 1] + grid[i][j], result[i - 1][j] + grid[i][j]); } } }
    return result[row- 1][col - 1]; }
    publicstaticvoidmain(String[]args) { Solution solution = new Solution();int grid[][] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}; System.out.println(solution.minPathSum(grid)); }}

    推荐阅读:

    5分钟理解DFS算法

    5分钟理解一致性哈希算法

    程序员必须知道的十种算法(上)

    程序员必须知道的十种算法(下)

    看完本文有收获?请分享给更多的人

    在技术成长的路上,让我们一起进步吧




    ----------------------------------------------------------------------------------------------------------------------
    我们尊重原创,也注重分享,文章来源于微信公众号:码农之屋,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
    ----------------------------------------------------------------------------------------------------------------------

    鲜花

    握手

    雷人

    路过

    鸡蛋

    yafeilinux和他的朋友们微信公众号二维码

    微信公众号

    专注于Qt嵌入式Linux开发等。扫一扫立即关注。

    Qt开源社区官方QQ群二维码

    QQ交流群

    欢迎加入QQ群大家庭,一起讨论学习!

    我有话说......