> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/minimum-path-sum.md).

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

```java
public class Solution {
    public int minPathSum(int[][] A) {
        if (A.length == 0)
            return 0;
        int[][] dp = new int[A.length][A[0].length];
        int row = A.length;
        int col = A[0].length;
        for (int i = row - 1; i >= 0; i--) {
            for (int j = col - 1; j >= 0; j--) {
                if (i == row - 1 && j == col - 1)
                    dp[i][j] = A[i][j];
                else if (i == row - 1)
                    dp[i][j] = A[i][j] + dp[i][j + 1];
                else if (j == col - 1)
                    dp[i][j] = A[i][j] + dp[i + 1][j];
                else
                    dp[i][j] = A[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[0][0];
    }
}
```