题解 | #最小体重积#

考察的知识点：动态规划；

解答方法分析：

1. 创建一个二维数组dp来保存中间结果，其中dp[i][j]表示从左上角到达位置(i, j)所经过路径上所有奶牛的体重积。
2. 初始化第一行和第一列的值，分别为从左上角到每个位置的体重积。
3. 使用双重循环计算其他位置的值，每次选择上方和左方路径中体重积较小的那个路径，再乘以当前位置的奶牛体重。
4. 返回dp[m-1][n-1]

所用编程语言：C++；

完整编程代码：↓

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型vector<vector<>>
     * @return long长整型
     */
    long long minPathProduct(vector<vector<int> >& cows) {
        int m = cows.size();
        int n = cows[0].size();
        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++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) * cows[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};