# 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.```

## 解法一：

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

## 解法二：

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

143 篇文章24 人订阅

0 条评论

## 相关文章

35950

17460

17430

33880

### 抽象类和接口的区别

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

222100

40380

21360

31760

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

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

7910

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

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

25430