Minimum Path Sum

Medium

dynamic-programmingmatrix

Given a grid of non-negative integers, find a path from top-left to bottom-right (moving only right or down) minimizing the sum of visited values. Return that sum.

Input

Line 1: r c
Next r lines: the grid rows

Output: the minimum path sum.

Example 1

Input:

Output:

1→3→1→1→1.

Example 2

Input:

2 3
1 2 3
4 5 6

Output:

Constraints

1 ≤ r, c ≤ 200
0 ≤ values ≤ 100

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Minimum Path Sum

Medium

dynamic-programmingmatrix

Given a grid of non-negative integers, find a path from top-left to bottom-right (moving only right or down) minimizing the sum of visited values. Return that sum.

Input

Line 1: r c
Next r lines: the grid rows

Output: the minimum path sum.

Example 1

Input:

Output:

1→3→1→1→1.

Example 2

Input:

2 3
1 2 3
4 5 6

Output:

Constraints

1 ≤ r, c ≤ 200
0 ≤ values ≤ 100

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.