Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The best path to a cell comes from the cheaper of the cell above and the cell to the left.
  2. 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]);
    }
}

Solve Minimum Path Sum online · All practice problems