题解 | #最小体重积#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

动态规划

题目解答方法的文字分析

这道题要求我们计算从左上角到右下角挤奶的路径上所有奶牛的体重积，并且要求路径积最小，同时需要注意溢出情况。

我们可以使用动态规划来解决该问题。定义一个 dp 数组，其中 dp[i][j] 表示从左上角到达位置 (i, j) 的路径上所有奶牛的体重积。我们可以根据上一个状态推导出当前状态，具体推导公式如下：

1. 对于左上角的位置 (0, 0)，dp[0][0] = cows[0][0]，表示从起始位置开始的路径上只有一头奶牛。
2. 对于第一行和第一列的位置，dp[i][0] = dp[i-1][0] * cows[i][0]，dp[0][j] = dp[0][j-1] * cows[0][j]，表示只有一条路径可达，累计奶牛体重积。
3. 对于其他位置 (i, j)，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) * cows[i][j]，表示到达当前位置有两条路径可选，我们选择体重积更小的路径。

最后，dp[m-1][n-1] 就表示从左上角到右下角挤奶的路径上所有奶牛的体重积，并且路径积最小。

由于可能涉及到大数相乘，需要注意溢出情况。在计算 dp[i][j] 时，我们可以用一个变量 minProduct 来表示 dp[i-1][j] 和 dp[i][j-1] 的较小值，然后再和当前位置的奶牛体重相乘。这样可以避免直接相乘导致的溢出问题。

本题解析所用的编程语言

C++

完整且正确的编程代码

class Solution {
public:
    long long minPathProduct(vector<vector<int>>& cows) {
        int m = cows.size();
        int n = cows[0].size();
        if (m == 0 || n == 0) {
            return 0;
        }

        vector<vector<long long>> dp(m, vector<long long>(n, 0));
        dp[0][0] = cows[0][0];

        // 初始化第一行和第一列
        for (int i = 1; i < m; ++i) {
            dp[i][0] = dp[i - 1][0] * cows[i][0];
        }

        for (int j = 1; j < n; ++j) {
            dp[0][j] = dp[0][j - 1] * cows[0][j];
        }

        // 动态规划计算其他位置的值，同时处理溢出情况
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                long long minProduct = min(dp[i - 1][j], dp[i][j - 1]);
                dp[i][j] = minProduct * cows[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！

我觉的不是我的问题@牛客周周