题解 | #最小体重积#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return long长整型
     */
    public long minPathProduct (int[][] cows) {
        // write code here
        int m = cows.length;
        int n = cows[0].length;

        long[][] dp = new long[m][n]; // 使用long类型，以防止乘积溢出

        dp[0][0] = cows[0][0];

        // Initialize the first row and first column
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] * cows[i][0];
        }
        for (int j = 1; j < n; j++) {
            dp[0][j] = dp[0][j - 1] * cows[0][j];
        }

        // Fill in the DP array using bottom-up approach
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) * cows[i][j];
            }
        }

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

知识点：

1. 动态规划：一种通过将问题分解成子问题，并存储子问题的解来解决问题的方法。
2. 二维网格：一个由行和列组成的矩阵结构，通常用来表示图形、地图等。

解题思路：

使用一个二维动态规划数组 dp 来存储从起点到每个位置的路径上所有奶牛体重积的最小值。我们通过初始化第一行和第一列的路径上奶牛体重积，然后根据相邻位置的最小值迭代填充 dp 数组。最终，我们返回 dp[m-1][n-1]。