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];
    }
}