题解 | #挤奶路径#

题目考察的知识点

考察动态规划算法

题目解答方法的文字分析

构建dp数组，dp[i][j]表示到达i，j位置的路径数。首先对于特殊情况进行特判（16行），初始化dp数组，第一列只能由上一列往下运动过来。随后对于内部位置进行遍历，状态转移方程是dp[i][j] = dp[i-1][j] + dp[i][j-1]（即（i,j）位置的路线数量由前一个位置和上一个位置的路线数量之和所决定的）。具体细节可再参看代码注释

本题解析所用的编程语言

使用Java解答

完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型二维数组 
     * @return int整型
     */
    public int uniquePathsWithObstacles (int[][] cows) {
        // write code here
        // dp[i][j]表示到达i，j位置的路径数
        int m = cows.length, n = cows[0].length;
        if(cows[0][0]==1) return 0; //起始节点有障碍物 无法行动
        int[][] dp = new int[m][n];
        for(int i=0; i<m; i++){
            if(cows[i][0]==1) break; //无法再向下运动
            dp[i][0] = 1; //初始化第一列
        }
        for(int j=0; j<n; j++){
            if(cows[0][j]==1) break; //无法再向右运动
            dp[0][j] = 1; //初始化第一列
        }
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(cows[i][j]==1) continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}