Practice › Dynamic Programming
Minimum Path Sum
Medium · Dynamic Programming · Asked at Amazon, Google, Goldman Sachs
Find a path from the top-left to the bottom-right of the grid, moving only right or down, that minimises the sum of the numbers on it. Print that sum.
Input
First line: r c. Next r lines: c non-negative integers.
Output
The minimum path sum.
Constraints
- 1 ≤ r, c ≤ 200
- 0 ≤ value ≤ 100
Example 1
Input
3 3 1 3 1 1 5 1 4 2 1
Output
7
Example 2
Input
2 3 1 2 3 4 5 6
Output
12
Hints
- The best path to a cell comes from the cheaper of the cell above and the cell to the left.
- dp[i][j] = grid[i][j] + min(dp[i−1][j], dp[i][j−1]); the first row and column can only be reached one way.
Approach
Fill the grid in row-major order. The first row only accumulates from the left and the first column only from above. Every other cell adds its value to the smaller of its top and left neighbours. Overwriting the grid in place (or using one row) keeps the extra memory small. The answer is the bottom-right cell.
Complexity: O(r·c) time · O(1) extra space (in place)
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int r, c;
cin >> r >> c;
vector<vector<long long>> g(r, vector<long long>(c));
for (auto &row : g)
for (auto &x : row) cin >> x;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (i == 0 && j == 0) continue;
if (i == 0) g[i][j] += g[i][j - 1];
else if (j == 0) g[i][j] += g[i - 1][j];
else g[i][j] += min(g[i - 1][j], g[i][j - 1]);
}
cout << g[r - 1][c - 1] << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
r, c = data[0], data[1]
g = [data[2 + i * c : 2 + (i + 1) * c] for i in range(r)]
for i in range(r):
for j in range(c):
if i == 0 and j == 0:
continue
if i == 0:
g[i][j] += g[i][j - 1]
elif j == 0:
g[i][j] += g[i - 1][j]
else:
g[i][j] += min(g[i - 1][j], g[i][j - 1])
print(g[r - 1][c - 1])Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int r = sc.nextInt(), c = sc.nextInt();
long[][] g = new long[r][c];
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) g[i][j] = sc.nextLong();
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++) {
if (i == 0 && j == 0) continue;
if (i == 0) g[i][j] += g[i][j - 1];
else if (j == 0) g[i][j] += g[i - 1][j];
else g[i][j] += Math.min(g[i - 1][j], g[i][j - 1]);
}
System.out.println(g[r - 1][c - 1]);
}
}