题解 | #最小体重积# java
最小体重积
https://www.nowcoder.com/practice/0980f806727e48f3b0253243416038c0
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]; dp[0][0] = cows[0][0]; 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]; } 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]; } }
编程语言:Java
知识点:动态规划
代码简短解释:使用二维数组 dp
来存储每个位置的最小路径乘积,然后通过循环遍历数组,逐步更新 dp
数组。首先,初始化第一行和第一列的路径乘积;然后,使用两层循环遍历剩余的位置,每个位置的最小路径乘积由其上方和左侧位置的较小值乘以当前位置的值得出。最后,返回右下角位置的最小路径乘积即可。