[LeetCode] 64. Minimum Path Sum

【原题】 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

【解释】 有一个mxn的数组,要求找到从左上到右下的最小的和为多少?

【思路】 基本思路和这题一样

public class Solution {
    public int minPathSum(int[][] grid) {
         int m=grid.length;
         int n=grid[0].length;
            int[][] dp=new int[m][n];
            dp[0][0]=grid[0][0];
            int sum=grid[0][0];
            for(int i=1;i<m;i++){    
                sum+=grid[i][0];
                dp[i][0]+=sum;
            }
            sum=grid[0][0];
            for(int j=1;j<n;j++){
                sum+=grid[0][j];
                dp[0][j]=sum;      
            }
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    dp[i][j]=Math.min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j]);
                }
            }
           return dp[m-1][n-1]; 
        }
}

若可以更改原数组则可以将空间复杂度降为O(1),见这里

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

编程范式 (Programming paradigm)

范,模范、典范也。范式即模式、方法。常见的编程范式有:函数式编程、程序编程、面向对象编程、指令式编程等。

2381
来自专栏NetCore

关于某道C#上机题的OO

前两天在园子里,有人出了一道《关于一道C#上机题的一点想法》,大概的意思呢是利用OO的思想来进行编程,接着又有一位朋友,也写了自己的答案,此朋友非常厉害,从类图...

2126
来自专栏专注研发

poj-1006-Biorhythms

人生来就有三个生理周期,分别为体力、感情和智力周期,它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天,人会在相应的方面表现出色。例如...

851
来自专栏海天一树

全国青少年信息学奥林匹克分区联赛(NOIP)竞赛大纲

* MS DOS与Windows的使用基础(在2013年后,很少出现与MS DOS相关内容)

1054
来自专栏WebHub

盘点那些奇形怪状的编程语言

有的语言是多面手,在很多不同的领域都能派上用场。这类编程语言叫 general-purpose language,简称 GPL。大家学过的编程语言很多都属于这一...

1772
来自专栏斑斓

哲思片段 | 设计中的变与不变

古希腊哲学家巴门尼德认为:“人的思想和言语都有一个载体,如果你在这一时间和另外一个时间想到或者谈到同样一件东西,那就说明这件东西在这段时间内没有变化,如有变化的...

3787
来自专栏Python小屋

Python实现大自然数分解为最多4个平方数之和(1)

问题描述:任意大自然数,总是能分解为最多4个平方数的和,所谓平方数是指它是一个自然数的平方。例如:72884 = 4^2 + 138^2 + 232^2,337...

2594
来自专栏Python爬虫实战

设计模式:抽象工厂模式

抽象工厂(Abstract Factory)模式提供一个创建一系列相关或相互依赖对象的接口,而无须指定它们具体的类。抽象工厂模式又称为Kit模式,属于对象创建型...

901
来自专栏牛客网

阿里 Java研发工程师[内推] 电话面试

3月20号 阿里巴巴 Java研发工程师[内部推荐] 电话面试 1. 自我介绍(问了我哪里人、去杭州工作有没有问题、什么时间可以去实习) 2. 介绍一下自己做过...

4309
来自专栏Albert陈凯

Scala兴衰史:暂时的没落或许是一个新的开始

5年前,Scala 似乎曾要成为编程语言中下一个佼佼者,因为它能够优雅得使用面向对象编程范式进行函数编程。 现如今,随着像 LinkedIn 和 Yammer ...

3454

扫码关注云+社区