【LeetCode】64. Minimum Path Sum

内容简介：【LeetCode】64. Minimum Path Sum

问题描述

https://leetcode.com/problems/minimum-path-sum/#/description

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.

算法

矩阵 m x n ，从左上角到右下角有很多条路径，每个位置都有一个数字，求路径上数字之和的最小值。

设 (i,j) 表示从 (0,0) 到 (i,j) 的所有路径上数字之和中的最小值，则有：

1. f(0,0) = grid[0][0]
2. f(i,0) = f(i-1,0) + grid[i-1][0],0<i<m ，第一列
3. f(0,j) = f(0,j-1) + grid[0][j-1],0<j<n ，第一行
4. f(i,j) = min(f(i-1,j), f(i,j-1)) + grid[i][j]，1<=i<m, 1<=j<n

代码

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

转载请注明出处 ： http://www.zgljl2012.com/leetcode-64-minimum-path-sum/

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

查看所有标签

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。