题解 | #挤奶路径2# 乘法原理 + DP

知识点

乘法原理 动态规划

思路

下面我们讨论DP解法。

首先由于只能向右或者向下移动，那么说明任意值为2的点的横纵坐标大小关系必须是一致的，也就是对于点（x1，y1）和（x2，y2）而言，如果存在（x1 < x2）且 (y1 > y2)的情况一定是无解的

排除掉这一点后，我们发现假如存在m个有牛的位置，他会把整个图分成若干段，每一段都是求从左上角到右下角的方案数，而且互不干扰，这可以用乘法原理解决。而每一部分求从左上角到右下角的方法数是很基本的DP，和上一道题是一样的。

最差的时间复杂度应该是没有牛的时候从左上角到右下角，此时的时间复杂度是

AC Code (c++)

#define x first
#define y second
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型vector<vector<>> 
     * @return int整型
     */
    using PII = pair<int, int>;
    vector<vector<int>> f;
    int uniquePathsWithCows(vector<vector<int> >& cows) {
        if (cows[0][0] == 1) return 0;
        int n = cows.size(), m = cows[0].size();
        f.resize(n, vector<int>(m, 0));
        vector<PII> pos;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                if (cows[i][j] == 2) {
                    if (pos.size() and (pos.back().x > i or pos.back().y > j)) {
                        return 0;
                    }
                    pos.emplace_back(i, j); 
                }
            }
        }
        if (pos.empty() or pos.back() != make_pair(n - 1, m - 1)) {
            pos.emplace_back(n - 1, m - 1);
        }
        int res = 1;
        PII last = {0, 0};
        for (auto& p: pos) {
            if (p == last) continue;
            res *= get(cows, last, p);
            last = p;
            cout << res << endl;
        }
        return res;
    }

    int get(vector<vector<int>>& g, const PII& st, const PII& ed) {
        for (int i = st.x; i <= ed.x; i ++) {
            for (int j = st.y; j <= ed.y; j ++) {
                if (i == st.x and j == st.y) {
                    f[i][j] = 1;
                    continue;
                }
                f[i][j] = 0;
                if (g[i][j] == 1) continue;
                if (i - 1 >= st.x) f[i][j] += f[i - 1][j];
                if (j - 1 >= st.y) f[i][j] += f[i][j - 1];
            }
        }
        return f[ed.x][ed.y];
    }
};