题解 | #最小体重积#

题目考察的知识点

考察动态规划

题目解答方法的文字分析

路径问题，求从左上角出发到达右下角的最小路径积。arr[i][j]表示到达（i，j）位置的最小路径积。虽然题目说的是四方向都能移动 但是想从左上角到右下角 最快或者说代价最小的还是每次选择向右或者向下移动。所以第一行只能由左侧移动过来，第一列只能由上方移动过来。而中间状态的动态转移过程应该是左侧和上方的最小值和当前位置的值进行乘积，即31行所示。最终返回右下角的值即可。

本题解析所用的编程语言

使用Java解答

完整且正确的编程代码

import java.util.*;


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