题解 | #最小体重积#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param cows int整型二维数组
     * @return long长整型
     */
    public long minPathProduct (int[][] cows) {
        // write code here
        int n = cows.length;
        int m = cows[0].length;
        // dp[i][j] 表示从0, 0到i, j位置所有牛的最小体重积
        long[][] dp = new long[n][m];
        dp[0][0] = cows[0][0];
        for (int i = 1; i < m; i++) {
            dp[0][i] = dp[0][i - 1] * cows[0][i];
        }
        for (int i = 1; i < n; i++) {
            dp[i][0] = cows[i][0] * dp[i - 1][0];
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                dp[i][j] = Math.min(
                    dp[i][j - 1],// 左边
                    dp[i - 1][j]// 上面
                ) * cows[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }
}

import java.util.*;


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

题目描述：

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

思路：

• 我们需要求从0，0位置到n-1，m-1位置的最小乘积。可以将这个位置分解为【求从0，0位置到n-2，m-1位置的最小乘积】和【求从0，0位置到n-1，m-2位置的最小乘积】；同样的道理，上面两个子问题也可以采取同样的策略分别分解为相似的两个子问题。满足动态规划的最优子结构
• 由于一个大问题都可以分解为两个相似的子问题，所以满足子问题重叠
• 在做出选择后，由于只能向下或向右进行移动，所以子问题的解永远只有一种，且后面的原问题不会影响子问题的解，所以满足无后效性
• 因此，我们可以采取动态规划的方式解决这个问题

解决方案：

• 定义dp[i][j]为从0，0位置到i，j位置的最小体重积
• 对于dp数组形成的二维表，它的第0行和第0列都是直接可以初始化的，因为规则是只能向相邻的右边或下面移动。
• 从左往右且从上往下（或从上往下从左往右都行，因为本问题对上面和左边的依赖权重是相同的，这里选择第一种）进行状态转移。dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) * cows[i][j];
• 根据dp数组的定义最后返回dp[n - 1][m - 1]就是最后的答案
• 注意由于返回值为long类型，所以我们需要开辟的dp数组而long类型，否则会导致int类型溢出

滚动dp：

• 由于上面是一行一行的进行状态转移的（当然也可以一列一列的进行转移），所以我们可以采用一维数组（long类型）进行状态转移
• 我们只需要保证第一行的时候dp数组是正确初始化的；第一行的时候，由于只能向右边移动，所以累乘得到每一个dp[i]位置的值
• 当到达不是第一行的某一行时，由于在第一列也是只能往下走，所以在每一行的第一列，都需要累乘上一行的积，得到本行第一列的值，然后继续向右边进行状态转移
• 当既不是第一行也不是某一行的第一列时，由于dp[i]的值还是上一行的累乘结果，所以原来的dp[i]就是上边的值，dp[i-1]是本行更新后的结果，所以状态转移方程是dp[i] = Math.min(dp[i - 1], dp[i]) * cows[i][j];
• 最后返回dp[m - 1]的值就是最终结果

滚动数组可以将二维空间压缩为一维空间，如果想要进最大程序的压缩，只需要判断行和列那个小然后取小的那个进行状态转移即可