Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Minimum path sum

Given a grid of height h and width w filled with integers, you are asked to find a path from the top-left to the bottom-right corner that minimizes the sum of numbers along the path. You are only allowed to move right or down.

 3 2 1 3 1 9 2 3 9 1 5 4

#### Input

The first line of the input contains two integers h and w (1 ≤ h, w ≤ 1000).
The next h lines contain w space-separated integers representing the values in the grid .

#### Output

The program should print the minimum possible sum to get from the top-left corner to the bottom-right corner.

#### Examples

 Input Output 3 4 3 2 1 3 1 9 2 3 9 1 5 4 15

#### Explanation

We can move: 3 → 2 → 1 → 2 → 3 → 4

Hint 1
The state in a dynamic programming problem can be a 2-dimensional array.
Hint 2
It can represent the best possible solution up to that coordinate (d[r][c] represents the best path to reach the row r and the column c).

Why doesn’t the greedy approach work here? Imagine if you always moved in the direction of the smallest possible value. What would be the issue there?

#### Constraints

Time limit: 1.5 seconds

Memory limit: 512 MB

Output limit: 1 MB