# 64.Minimum-Path-Sum

## 题目地址

https://leetcode.com/problems/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.``````

## 代码

### Approach 1: DFS - bottom up

Complexity Analysis

• Time complexity : O(2^(_m+_n)). For every move, we have atmost 2 options.

• Space complexity : O(m+n). Recursion of depth m+n.

``````class Solution {
public int minPathSum(int[][] grid) {
return calculate(grid, 0, 0);
}

private int calculate(int[][] grid, int i, int j) {
if (i == grid.length || j == grid[0].length) {
return Integer.MAX_VALUE; // over the boundary
}

if (i == grid.length - 1 && j == grid[0].length - 1) {
return grid[i][j]; // reach the end
}

return grid[i][j] + Math.min(calculate(grid, i + 1, j),
calculate(grid, i, j + 1));
}

}``````

### Approach #2 DFS - top up

``````class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid[0] == null) return 0;

int r = grid.length - 1;
int c = grid[0].length - 1;

return dfs(grid, r, c);
}

private int dfs(int[][] grid, int r, int c) {
if (r == 0 && c == 0)        return grid[0][0];

if (r == 0) {
return dfs(grid, r, c - 1) + grid[r][c];
}

if (c == 0) {
return dfs(grid, r - 1, c) + grid[r][c];
}

return grid[r][c] + Math.min(dfs(grid, r - 1, c),
dfs(grid, r, c - 1));
}
}``````

### Approach #3 DP

Complexity Analysis

• Time complexity : O(mn). We traverse the entire matrix once.

• Space complexity : O(mn). Another array of row size is used.

``````class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid[0] == null) return 0;

int R = grid.length;
int C = grid[0].length;

int[][] dp = new int[R][C];
dp[0][0] = grid[0][0];
for (int i = 1; i < R; i++) {
dp[i][0] = grid[i][0] + dp[i - 1][0];
}
for (int i = 1; i < C; i++) {
dp[0][i] = grid[0][i] + dp[0][i - 1];
}

for (int i = 1; i < R; i++) {
for (int j = 1; j < C; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}

return dp[R - 1][C - 1];
}
}``````

### Approach #4 Dynamic Programming 2D

``````public class Solution {
public int minPathSum(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
int[][] dp = new int[R][C];
// 从终点往起点走
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (i == R - 1 && j != C - 1) {
dp[i][j] = grid[i][j] + dp[i][j + 1]; // 只能往右走
} else if(j == C - 1 && i != R - 1) {
dp[i][j] = grid[i][j] + dp[i + 1][j]; // 只能往下走
} else if(j != C - 1 && i != R - 1) {            // 往右 + 往下
dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
} else {    // 终点-终点的距离
dp[i][j] = grid[i][j];
}
}
}
return dp[0][0];
}
}``````

### Approach #5 Dynamic Programming 1D

Complexity Analysis

• Time complexity : O(mn). We traverse the entire matrix once.

• Space complexity : O(n). Another array of row size is used.

``````class Solution {
public int minPathSum(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
int[] dp = new int[C];
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (i == R - 1 && j != C - 1) {
dp[j] = grid[i][j] +  dp[j + 1]; // 只能往右
} else if (j == C - 1 && i != R - 1) {
dp[j] = grid[i][j] + dp[j]; // 只能往下
} else if (j != C - 1 && i != R - 1) {     // 往下 + 往右
dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
} else {    // 终点
dp[j] = grid[i][j];
}
}
}

return dp[0];
}
}``````

### Approach #6 Dynamic Programming (Without Extra Space)

Complexity Analysis

• Time complexity : O(mn). We traverse the entire matrix once.

• Space complexity : O(1). No extra space is used.

``````public class Solution {
public int minPathSum(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
for (int i = R - 1; i >= 0; i--) {
for (int j = C - 1; j >= 0; j--) {
if (i == R - 1 && j != C - 1) {
grid[i][j] = grid[i][j] +  grid[i][j + 1];
} else if(j == C - 1 && i != R - 1) {
grid[i][j] = grid[i][j] + grid[i + 1][j];
} else if(j != C - 1 && i != R - 1) {
grid[i][j] = grid[i][j] + Math.min(grid[i + 1][j], grid[i][j + 1]);
}
}
}
return grid[0][0];
}
}``````

Last updated