题解 | #最小体重积#

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


    }
};

dp[i][j]表示第i行j列的最小体重积，将第一行和第一列初始化，每个值都为当前数乘以前一个dp值，然后遍历二维数组更新dp，条件是取上边和左边的较小dp与当前位置的值的积。最后一个位置就是这个矩阵的最小积。