首页 > 试题广场 >

最小体重积

[编程题]最小体重积

热度指数：787 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一个农场中，农民们在一片田地里放养了一些奶牛。这片田地可以看作是一个m x n的网格，每个位置都有一头奶牛，每头奶牛都有一个体重。现在农民想知道，如果他每天从左上角到右下角去挤奶，每次只能移动到右边或者下面的相邻位置，那么他需要经过的路径上所有奶牛的体重积是多少？

示例1

输入

[[1,3,1],[1,5,1],[4,2,1]]

输出

说明

因为路径 1→3→1→1→1 的总体重积最小。

示例2

输入

[[1,2,3],[4,5,6]]

输出

说明

因为路径 1→2→3→6 的总体重积最小。

备注:

m == cows.length
n == cows[i].length
1 <= m, n <= 30
1 <= cows[i][j] <= 100

算法知识视频讲解

C++

retyrn

这题题面目前要求可以上下左右移动。用DP的方法是错误的。我认为正解是dijkstra。

比如这样的数据

1 1 1 9

9 9 1 9

9 1 1 9

9 1 9 9

9 1 1 1

明显存在一条积为1的通路。

hack数据：

[[1,1,1,9],[9,9,1,9],[9,1,1,9],[9,1,9,9],[9,1,1,1]]

发表于 2023-08-02 14:35:23 回复(2)

C++

虚数五行区

动态规划

#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];
    }
};

发表于 2024-05-28 17:10:22 回复(0)

Java

小谷围做题家

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cows int整型二维数组 
     * @return long长整型
     */
    public long minPathProduct (int[][] cows) {
        int m=cows.length,n=cows[0].length;
        long[][] mat=new long[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                mat[i][j]=cows[i][j];
            }
        }
        for(int i=1;i<m;i++){
            mat[i][0]*=mat[i-1][0];
        }
        for(int j=1;j<n;j++){
            mat[0][j]*=mat[0][j-1];
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                mat[i][j]*=Math.min(mat[i-1][j],mat[i][j-1]);
            }
        }
        return mat[m-1][n-1];
    }
}

发表于 2023-08-09 18:14:00 回复(0)