题解 | #最小体重积#

知识点：动态规划

思路：

首先，我们创建一个二维数组arr来保存从起点到每个节点的最小路径乘积。

然后，我们初始化arr数组的第一行和第一列。第一行的每个元素等于前一个元素与当前节点权值的乘积，因为只能向右移动。同样地，第一列的每个元素等于前一个元素与当前节点权值的乘积，因为只能向下移动。起点的乘积保持不变。

接下来，我们使用两重循环遍历数组的剩余部分。对于每个节点，我们计算从上方节点和左方节点中选择乘积值小的那个，然后再乘以当前节点的权值。这样得到的就是从起点到当前节点的最小路径乘积。

最后，我们返回arr数组中最后一个元素，即终点的最小路径乘积。

对于给定的输入矩阵cows = {{1, 2, 3, 4}, ...}，使用动态规划的解法可以得到从起点到终点的最小路径乘积为8。

编程语言：java

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[][] arr = new long[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(arr[i], 1);
        }
        arr[0][0] = cows[0][0];
        for (int i = 1; i < n; i++) {
            arr[0][i] = cows[0][i] * arr[0][i - 1];
        }
        for (int i = 1; i < m; i++) {
            arr[i][0] = cows[i][0] * arr[i - 1][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                arr[i][j] = Math.min(arr[i - 1][j], arr[i][j - 1]) * cows[i][j];
            }
        }
        return arr[m - 1][n - 1];
    }
}