# 64.Minimum-Path-Sum

## 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 : &#x4F;*(2^(\_m*+\_n)). For every move, we have atmost 2 options.
* Space complexity : O(m+n). Recursion of depth m+n.

```java
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

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

```java
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

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

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

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


---

# 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://wentao-shao.gitbook.io/leetcode/dynamic-programming/1.position/64.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.