给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

典型的动态规划，递推公式：

dp[i][j] = grid[i][j]                                     (i=0,j=0)
dp[i][j] = dp[i-1][j]+grid[i][j]                          (i>0,j=0)
dp[i][j] = dp[i][j-1]+grid[i][j]                          (i=0,j>0)
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]       (i>0,j>0)

public class 最小路径和64 {
	public static int minPathSum(int[][] grid) {
	        if(grid == null) return 0;
	        
	        int m = grid.length;
	        int n = grid[0].length;
	        int[][] dp = new int[m][n];
	        
	        for(int i = 0;i<m;i++){
	            for(int j = 0;j<n;j++){
	                if(i == 0 && j == 0){
	                    dp[i][j] = grid[i][j];
	                }else if(i == 0 && j!=0){
	                    dp[i][j] = dp[i][j-1]+grid[i][j];
	                }else if(i!=0 && j==0){
	                    dp[i][j] = dp[i-1][j]+grid[i][j];
	                }
	                else{
	                    dp[i][j] = grid[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
	                }
	            }
	        }
	        return dp[m-1][n-1];
	    }
	    //测试 main方法入口
	    public static void main(String[] args) {
		int[][] grid = {{1,3,1},
		  {1,5,1},
		  {4,2,1}};
		int minPathSum2 = minPathSum2(grid);
		System.out.println(minPathSum2);
	}
}

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
   示例 2:

输入: m = 7, n = 3
输出: 28

很经典的一道动态规划

• 当终点在边界时，肯定只有一条路，因此

if(i == 0 || j == 0){
	dp[i][j] = 1;
}

• 当终点不在边界时，当前终点的路数等于它上面和左边节点的路数之和，即：

dp[i][j] = dp[i-1][j]+dp[i][j-1];

public class 不同路径62 {

	public static int uniquePaths(int m, int n) {
	        int[][] dp = new int[m][n];
	        for(int i = 0;i<m;i++){
	            for(int j = 0;j<n;j++){
	                if(i == 0 || j == 0){
	                    dp[i][j] = 1;
	                }else{
	                    dp[i][j] = dp[i-1][j]+dp[i][j-1];
	                }
	            }
	        }
	        return dp[m-1][n-1];
	    }
	
	public static void main(String[] args) {
		int uniquePaths = uniquePaths(3,2);
		System.out.println(uniquePaths);
	}
}

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1.向右 -> 向右 -> 向下 -> 向下
2.向下 -> 向下 -> 向右 -> 向右

还是典型的动态规划，相比上题，增加了障碍。

分开边界和内部的计算，这样会比较清晰。

• 边界，如果边界上某点有障碍，则该到该点的路数就为0；如果没障碍，则到该点的路数等于到它前面一个点的路数。代码中对应：

//行（左边框）
for(int i = 1;i<rows;i++){
     if(obstacleGrid[i][0] == 1){
         dp[i][0] = 0;
     }else{
         dp[i][0] = dp[i-1][0];
     }
 }
        
//列（上边框）
for(int i = 1;i<columns;i++){
    if(obstacleGrid[0][i] == 1){
        dp[0][i] = 0;
    }else{
        dp[0][i] = dp[0][i-1];
    }
}

• 内部，如果内部某点有障碍，则到达该点的路数为0；如果没障碍，则到达该点的路数等于到达它上面节点和左边节点的路数之和。代码中对应：

//行列（内部）
for(int i=1;i<rows;i++){
      for(int j = 1;j<columns;j++){
          dp[i][j] = obstacleGrid[i][j] == 1?0:dp[i-1][j]+dp[i][j-1];
      }
  }

public class 不同路径二63 {
	
	public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if(obstacleGrid == null||obstacleGrid.length == 0) return 0;
        int rows = obstacleGrid.length;
        int columns = obstacleGrid[0].length;
       
        int[][] dp = new int[rows][columns];
        
        if(obstacleGrid[0][0] == 1){
            dp[0][0] = 0;
        }else{
            dp[0][0] = 1;
        }
        
        //行（左边框）
        for(int i = 1;i<rows;i++){
            if(obstacleGrid[i][0] == 1){
                dp[i][0] = 0;
            }else{
                dp[i][0] = dp[i-1][0];
            }
        }
        
         //列（上边框）
        for(int i = 1;i<columns;i++){
            if(obstacleGrid[0][i] == 1){
                dp[0][i] = 0;
            }else{
                dp[0][i] = dp[0][i-1];
            }
        }
        
        //行列（内部）
        for(int i=1;i<rows;i++){
            for(int j = 1;j<columns;j++){
                dp[i][j] = obstacleGrid[i][j] == 1?0:dp[i-1][j]+dp[i][j-1];
            }
        }
        
        return dp[rows-1][columns-1];
    }
    
	//入口方法 main
	public static void main(String[] args) {
		int[][] obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}};
		int uniquePathsWithObstacles = uniquePathsWithObstacles(obstacleGrid);
		System.out.println(uniquePathsWithObstacles);
	}
}

输出结果2