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

相关文章

来自专栏ascii0x03的安全笔记

【C】用C语言提取bmp图片像素,并进行K-means聚类分析——容易遇到的问题

关于bmp图片的格式,网上有很多文章,具体可以参考百度百科,也有例子程序。这里只提要注意的问题。 (1)结构体定义问题:首先按照百度百科介绍的定义了结构体,但是...

4036
来自专栏hightopo

玩转 HTML5 下 WebGL 的 3D 模型交并补

901
来自专栏Windows Community

New UWP Community Toolkit - Staggered panel

概述 前面 New UWP Community Toolkit 文章中,我们对 2.2.0 版本的重要更新做了简单回顾,其中简单介绍了 Staggered pa...

3016
来自专栏数据处理

proc-tabulate

982
来自专栏Jack-Cui

第十二天、选择排序

题目 用选择排序法对一组数据由小到大进行排序,数据分别为526、36、2、369、56、45、78、92、125、52 1、程序分析选择排序的基本算法是从待...

1720
来自专栏進无尽的文章

绘图-Core Graphics

CGContext又叫图形上下文,相当于一块画布,以堆栈形式存放,只有在当前context上绘图才有效。iOS有分多种图形上下文,其中UIView自带提供的在d...

603
来自专栏程序员互动联盟

【专业技术】Android平台下使用OpenGL

存在问题: 安卓平台下如何使用opengl? 解决方案: 1、GLSurfaceView GLSurfaceView是Android应用程序中实现OpenGl画...

3586
来自专栏点滴积累

geotrellis使用(十五)使用Bokeh进行栅格数据可视化统计

Geotrellis系列文章链接地址http://www.cnblogs.com/shoufengwei/p/5619419.html 目录 前言 实现方案 ...

3137
来自专栏非著名程序员

Android 属性动画详解,属性动画基本用法

Hello,大家好,今天又来装逼了,装逼也上瘾啊,最近公司不是特别忙,我想这也就是我出来装逼的最好时机吧!额,,哈哈,进入正题。如有疑问欢迎留言,如有谬误欢迎批...

1985
来自专栏mathor

LeetCode42. 接雨水

 有人说用贪心,我觉得这是一个单调栈的板子题,构建一个单调递减栈(栈底到栈顶是递减的),要想能够收集雨水,栈中至少要两个数字,才能形成一个坑,先pop一个数...

1062

扫码关注云+社区