LintCode 最小路径和题目分析代码

题目

给定一个只含非负整数的m*n网格,找到一条从左上角到右下角的可以使数字和最小的路径。

** 注意事项 你在同一时间只能向下或者向右移动一步 **

分析

这是一道典型的动态规划的题目。 我们从尾分析,达到右下角的只有两种可能,一种是通过向下走到右下角,一种是通过向右走到右下角。那么到达右下角的最小代价,就是这两种情况下的相对小的那个加上右下角这一步的代价。 f(i,j) = MIN(f(i-1,j),f(i,j-1)) + grid(i,j)

代码

public class Solution {
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        // write your code here
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i=1;i<m;i++)
            dp[i][0] = dp[i-1][0] + grid[i][0];
        for(int j=1;j<n;j++)
            dp[0][j] = dp[0][j-1] + grid[0][j];
        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][j];
        return dp[m-1][n-1];
    }
    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

斯坦纳树小结

1670
来自专栏开心的学习之路

神经网络体系搭建(四)——快速上手TensorFlow

本篇是神经网络体系搭建的第四篇,解决体系搭建的TensorFlow相关问题,详见神经网络体系搭建(序) ? TensorFlow安装 建议用Anacond...

3455
来自专栏WindCoder

TensorFlow入门:一篇机器学习教程

TensorFlow是一个由Google创建的开源软件库,用于实现机器学习和深度学习系统。这两个名称包含一系列强大的算法,它们共享一个共同的挑战——让计算机学习...

3491
来自专栏人工智能LeadAI

人脸识别 | 卷积深度置信网络工具箱的使用

本文主要以ORL_64x64人脸数据库识别为例,介绍如何使用基于matlab的CDBN工具箱。至于卷积深度置信网络(CDBN,Convolutional Dee...

4445
来自专栏简书专栏

基于tensorflow+CNN的垃圾邮件文本分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 CNN是convolutional neural netwo...

5363
来自专栏瓜大三哥

视频压缩编码技术(H.264) 之哈夫曼编码

第二步,将两个最小概率组成一组,划成2 个分支域,并标以0 和1;再把2 个分支域合并成1个支域,标以两个概率之和;

1192
来自专栏简书专栏

基于tensorflow+RNN的MNIST数据集手写数字分类

tensorflow是谷歌google的深度学习框架,tensor中文叫做张量,flow叫做流。 RNN是recurrent neural network的简...

1743
来自专栏mwangblog

开始使用Octave

2184
来自专栏懒人开发

(1)James Stewart Calculus 5th Edition:Functions and Models

1463
来自专栏TensorFlow从0到N

TensorFlow从1到2 - 5 - 非专家莫入!TensorFlow实现CNN

当看到本篇时,根据TensorFlow官方标准《Deep MNIST for Experts》,你已经达到Expert Level,要恭喜了。 且不说是否夸大...

1.5K9

扫码关注云+社区

领取腾讯云代金券