LeetCode <dp>64. Minimum Path Sum

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.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

题目大意:求矩阵中的最小的路径

思路:这是一个典型的动态规划问题

解法一:

本解法的空间复杂度为O(m*n).

    int sum = 0;
    int [][] sss ;
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length ==0) return 0;
        sss = new int[grid.length][grid[0].length];
        return minPathSum_recursion(grid,0,0);
    }

 
    public int minPathSum_recursion(int[][] grid,int m ,int n) {
        if (m==grid.length-1) {
            int a = 0;
            for (int i = n;i<grid[0].length;i++){
                a = a + grid[m][i];
            }
            return a;
        }

        if (n == grid[0].length-1) {
            int b = 0;
            for (int i = m;i<grid.length;i++){
                b = b + grid[i][n];
            }
            return b;
        }
        if (sss[m][n] == 0){
            sss[m][n] = sum + grid[m][n] + Math.min(minPathSum_recursion(grid,m+1,n),minPathSum_recursion(grid,m,n+1));
        }
        return sss[m][n];
    }

解法二:

本解法的空间复杂度是min{m,n}.

    public int minPathSum(int[][] grid) {
        if (grid == null ||grid.length ==0|| grid[0].length ==0) return 0;
        int min = Math.min(grid.length,grid[0].length);
        int max = Math.max(grid.length,grid[0].length);
        int [] arr = new int[min];
        boolean rowlonger = grid.length == max; // 行数大于列数
        arr[0] = grid[0][0];
        for (int i = 1;i<min;i++){
            arr[i] = arr[i-1] + (rowlonger?grid[0][i]:grid[i][0]);
        }

        for (int i=1;i<max;i++){
            arr[0] = arr[0]+(rowlonger?grid[i][0]:grid[0][i]);
            for (int j = 1; j<min;j++){
                arr[j] = Math.min(arr[j-1],arr[j])+(rowlonger?grid[i][j]:grid[j][i]);
            }
        }
        return arr[min-1];
    }

这种压缩的方法适用于只求结果不求过程的题目,如果要求输出路径,那么还是需要使用解法一的。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

Java面试系列5

一、是否可以继承String类? String类是final类故不可以继承。 二、面向对象的特征有哪些方面 1.抽象: 抽象就是忽略一个主题中与当前目标无关的...

35950
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

17460
来自专栏Java后端技术栈

Java提供的排序算法是怎么实现的?快排?

前几天整理的一套面试题,其中有一个问题就是Java的JDK中我们见到的Collections.sort()和Arrays.sort()这两个排序算法的实现方式是...

17430
来自专栏趣谈编程

选择排序

面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

33880
来自专栏CSDN技术头条

抽象类和接口的区别

【编者按】本文作者是Sebastian Malaca,是面向对象编程的狂热者,不断深化研究整洁代码和高代码质量。本文中,作者通过多个方面深入剖析抽象类和接口的区...

222100
来自专栏个人随笔

Java 关于接口的那点事儿

接口的应用 接口是一种能力 关键字:interface 语法:  public interface MyInterface{   public void ...

40380
来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

21360
来自专栏申龙斌的程序人生

零基础学编程028:面向对象编程OOP

在《零基础学编程021:获取股票实时行情数据》一节中,我们想获取6支股票的行情数据,在《零基础学编程022:函数的世界》里我们能够把重复性的代码封装为一个函数p...

31760
来自专栏Android机动车

设计模式——抽象工厂模式

● 为创建一组相关或依赖的对象提供一个接口,而无需指定他们的具体类型。是工厂方法模式的升级版。

7910
来自专栏Albert陈凯

Scala如何改变了我的编程风格:从命令式到函数式

51CTO编辑推荐: Scala编程语言专题 【51CTO快译】编者前言:这篇文章最初写于2008年底,作者Bill Venners一方面是美国著名开发网站A...

25430

扫码关注云+社区

领取腾讯云代金券