首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode <dp>64. Minimum Path Sum

LeetCode <dp>64. Minimum Path Sum

原创
作者头像
大学里的混子
修改2018-11-15 14:59:33
6540
修改2018-11-15 14:59:33
举报
文章被收录于专栏:LeetCodeLeetCode

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];
    }

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

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 64. Minimum Path Sum
    • 解法一:
      • 解法二:
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档