题解 | #机器人走方格II#

/*
标准dp，
注意边界条件和状态转移中遇到障碍时的处理
*/
    public int countWays(int[][] map, int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        //base condition
        int flag = 0;
        for(int i = m - 1 ; i >= 0; i --){
            if(map[i][n - 1] != 1)
                flag = 1;
            if(flag == 0)   dp[i][n - 1] = 1;
            else   break;
        }
        flag = 0;
        for(int i = n - 1; i >= 0; i --){
            if(map[m - 1][i] != 1)
                flag = 1;
            if(flag == 0)   dp[m - 1][i] = 1;
            else  break;
        }        

        //condition transfer
        for(int i = m - 2; i >= 0 ; i --){
            for(int j = n - 2; j >= 0 ; j --){
                if(map[i][j] != 1) continue;
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0] % 1000000007;
    }