题解 | #最小体重积#

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

一、题目考察的知识点

二、题目解答方法的文字分析

这个题目只不过把加法换成乘法，但是本质还是一样的用dp思想

从dp[0][1]=1开始，遍历计算每一个位置上的最小乘积，每次选择上方 (i-1, j) 和左方 (i, j-1) 中较小的乘积，然后再乘以 cows[i-1][j-1]，得到 dp[i][j]。

三、本题解析所用的编程语言

c++