Given a m x n grid filled with non-negative numbers, write a program to find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Problem Note

  • You can only move either down or right at any point in time.

Example 1

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

Example 2

Input:
[   
  [1, 2, 8], 
  [4, 1, 5],  
  [1, 2, 3] 
] 
Output: 9 
Explanation: The path 1→2→1→2→3 minimizes the sum.