题解 | #最小体重积#

思路

动态规划

知识点

设n为行数，m为列数。

我们发现，第一行只能由左侧的走过来，第一列只能由上侧的走过来，其余的都能且只能由上侧或左侧的走过来。

所以，我们可以使用dp数组来维护最小的积。

对于dp[i][j]，有: =

据此，先初始化，在进行状态转移即可。dp[n-1][m-1]即为答案（注意下标从0开始）

记得开long long

代码c++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型vector<vector<>>
     * @return long长整型
     */
    long long minPathProduct(vector<vector<int> >& cows) {
        // write code here
        long long int dp[35][35];

        int n = cows.size();
        int m = cows[0].size();
        dp[0][0] = cows[0][0];
        for (int i = 1; i < n;i++)dp[i][0] = cows[i][0] * dp[i - 1][0]; //第一列
        for (int j = 1; j < m; j++)dp[0][j] = cows[0][j] * dp[0][j - 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][j];
            }
        }
        
        return dp[n - 1][m - 1];
    }
};