[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 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

左手用R右手Python系列5——数据切片与索引

今天这篇跟大家分享我的R VS Pyhton学习笔记系列5——数据索引与切片。 我之前分享过的所有学习笔记都不是从完全零基础开始的,因为没有包含任何的数据结构与...

3635
来自专栏葡萄城控件技术团队

如何在保留装箱对象的前提下修改值

有人问如何在保留装箱对象的前提下修改值? 场景: object obj = 100; Console.WriteLine("original object va...

1907
来自专栏Python

Django——model基础

ORM 映射关系:     表名 <-------> 类名 字段 <-------> 属性     表记录 <------->类实例对象...

16910
来自专栏SHERlocked93的前端小站

JS 活学活用正则表达式

网上的帖子大多深浅不一,甚至有些前后矛盾,在下的文章都是学习过程中的总结,如果发现错误,欢迎留言指出~

1122
来自专栏王硕

原 PostgreSQL的系统函数分析记录

893
来自专栏闵开慧

pig操作与注意事项

grunt> A = load 'hdfs://192.168.0.118:9000/user/hadoop/data.txt' as (name:charar...

2523
来自专栏滕先生的博客

OC最实用的runtime总结,面试、工作你看我就足够了!前言什么是runtime?如何应用运行时?

32412
来自专栏程序员宝库

关于 Java 你不知道的 10 件事

作为 Java 书呆子,比起实用技能,我们会对介绍 Java 和 JVM 的概念细节更感兴趣。因此我想推荐 Lukas Eder 在 jooq.org 发表的原...

2815
来自专栏chenssy

【死磕Sharding-jdbc】---group by结果合并(2)

在sharding-jdbc源码之group by结果合并(1)中主要分析了sharding-jdbc如何在GroupByStreamResultSetMerg...

792
来自专栏王硕

原 PostgreSQL的基础数据类型分析记录

1031

扫码关注云+社区