package dynamic;

/**题目:路径数量,含障碍物
 * 题目给定一个m*n的二维数组,数组值有0和1,要求从左上角走到右下脚的路径和,
 * 只能向右和向下走,并且数组值只有为0时候该路径才允许走
 * @Author Gavin
 * @date 2022年01月09日 16:35
 */
public class solution_7 {
 /**
 * 解题思路:动态规划题
 * 首先得到状态方程,我们可以得出如下的结论
 * 第0行到第0列上面所有的值都是0的话那么这行上面的所有路径都是1,如果中间i为1的话,
 * 那么从i到末尾的路径都是0
 * 同理第i行到第0列
 */
 //Time:O(m*n) Space:O(m*n)
 public int solution(int[][] grid){
 int m=grid.length,n=grid[0].length;
 int[][] d=new int[m][n];
 d[0][0]=grid[0][0]==1?0:1;
 for (int i = 1; i <m ; i++) {
 d[i][0]=grid[i][0]==1?0:d[i-1][0];
 }
 for (int j = 0; j < n; j++) {
 d[0][j]=grid[0][j]==1?0:d[0][j-1];
 }

 for (int i = 1; i <m ; i++) {
 for (int j = i; j < n; j++) {
 d[i][j]=grid[i][j]==1?0:d[i-1][j]+d[i][j-1];
 }
 }
 return d[m-1][n-1];
 }
}