题解 | #挤奶路径2#

题目考察的知识点：动态规划

题目解答方法的文字分析：从起点到必经点的路径，再从必经点到终点的路径；创建一个dp表，然后初始化，找到2的位置，在2的位置继续初始化，然后再寻找路径，到终点即可。

本题解析所用的编程语言：c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector<vector<>> 
     * @return int整型
     */
    int uniquePathsWithCows(vector<vector<int> >& cows) {
        // write code here
    int m = cows.size(), n = cows[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	//第一次初始化
    dp[0][1] = 1;
    int i = 0, j = 0;
    for (i = 1; i <= m; ++i)
    {
        for (j = 1; j <= n; ++j)
        {
            if (cows[i - 1][j - 1] == 2)
                break;
            if (cows[i - 1][j - 1] != 1)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
        if (j <= n && cows[i - 1][j - 1] == 2)
            break;
    }
	  //第二次初始化
    int tmp = dp[i - 1][j];
    for (int k = j - 1; k <= n; ++k)
            dp[i - 1][k] = 0;

    dp[i - 1][j] = tmp;
    for (int a = i; a <= m; ++a)
    {
        for (int b = j; b <= n; ++b)
        {
            if (cows[a - 1][b - 1] != 1)
                dp[a][b] = dp[a - 1][b] + dp[a][b - 1];
        }
    }
    return dp[m][n];
    }
};