Minimum Path Sum - Leetcode

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：找到代价最小的路径。从左上角第一个开始，这个是定局。+ min(向左，向下)，保证总和最小。这样就要使用到深搜的思想（要走到底才能确定最终答案）F(i,j) = min{F(i-1,j) , F(i, j-1)}+(i,j) 这个是dp的思想。

public class Solution {public int minPathSum(int[][] grid) {if (grid.length < 1 || grid[0].length < 1)return 0;int[][] f = new int[grid.length][grid[0].length];f[0][0] = grid[0][0];for (int i = 1; i < grid.length; i++)f[i][0] = grid[i][0]+f[i-1][0];for (int j = 1; j < grid[0].length; j++)f[0][j] = grid[0][j]+f[0][j - 1];for (int i = 1; i < grid.length; i++) {for (int j = 1; j < grid[0].length; j++) {f[i][j] = grid[i][j]+Math.min(f[i - 1][j], f[i][j - 1]);}}return f[grid.length - 1][grid[0].length - 1];}
}