题解 | #最小体重积#

#include <climits>
#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,INT_MAX));
        // 初始化左上角元素
        dp[0][0] = (long long)cows[0][0];
        // 初始化第一行
        for(int i=1; i<n; ++i)
            dp[0][i] = dp[0][i-1]*(long long)cows[0][i];
        // 初始化第一列
        for(int i=1; i<m; ++i)
            dp[i][0] = dp[i-1][0]*(long long)cows[i][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]) * (long long)cows[i][j];
        }

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