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

## Analysis

与 Unique Paths很相似，不过路径有了权重，因此在初始化和状态转移方程上稍有区别：

**状态**：`dp[i][j]` - 从起点到达(i, j)的最小路径和Min Path Sum\
**状态转移方程**: `dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];` - 左侧`(i, j - 1)`和上方 `(i - 1, j)`位置的路径和较小值，加上`(i, j)` 位置的权重\
**初始条件**: `dp[0][0] = grid[0][0]`, `dp[i][0] = dp[i - 1][0] + grid[i][0]; (i = 0, ... m - 1)`, `dp[0][j] = dp[0][j - 1] + grid[0][j]; (j = 0, ..., n - 1)`

**答案**：`dp[m - 1][n - 1]` 即终点位置

## Solution

DP - O(mn) space, O(mn) time (4 \~ 6ms 51.84% AC)

```java
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];

    }
}
```

DP - without extra space (reusing grid\[]\[] array itself)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/dynamic_programming/minimum-path-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.