# 64. Minimum Path Sum

## 1. Question

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.

## 2. Examples

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.


Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12


## 3. Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• 0 <= grid[i][j] <= 100

## 5. Solutions

dp

class Solution {
public int minPathSum(int[][] grid) {
int[][] res = new int[grid.length][grid[0].length];
for (int i = 0; i < res.length; i++) {
for (int j = 0; j < res[0].length; j++) {
if (i == 0 && j != 0) {
res[i][j] = res[i][j - 1] + grid[i][j];
} else if (i != 0 && j == 0) {
res[i][j] = res[i - 1][j] + grid[i][j];
} else if (i == 0 && j == 0) {
res[i][j] = grid[0][0];
} else {
res[i][j] = 0;
}
}
}

for (int i = 1; i < res.length; i++) {
for (int j = 1; j < res[0].length; j++) {
if (res[i][j - 1] < res[i - 1][j]) {
res[i][j] = res[i][j - 1] + grid[i][j];
} else {
res[i][j] = res[i - 1][j] + grid[i][j];
}
}
}

return res[grid.length - 1][grid[0].length - 1];

}
}