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

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

 

1 public class Solution { 2     public int minPathSum(int[][] grid) { 3         int m = grid.length,n = grid[0].length; 4         if(m == 0 || n == 0) return 0; 5         int[][] tmp = new int[m][n]; 6         int cnt = 0; 7         for(int i = 0; i < n; i++){ 8             cnt += grid[0][i]; 9             tmp[0][i] = cnt;10         }11         cnt = 0;12         for(int i = 0; i < m; i++){13             cnt += grid[i][0];14             tmp[i][0] = cnt;15         }16         17         for(int i = 1;i < m; i++){18             for(int j = 1;j < n; j++){19                 tmp[i][j] = Math.min(tmp[i-1][j],tmp[i][j-1]) + grid[i][j];20             }21         }22         return tmp[m-1][n-1];23     }24 }

非常自然能想到的解法，一遍AC。