题解 | #最小三角路径和#
最小三角路径和
https://www.nowcoder.com/practice/cc6afb95517f460cb785397c36ae4a9b
知识点：动态规划
对于每一行来说，我们最小的路径和取决于上一行的元素和大小，我们对当前行的每一个元素进行判断，取其上一行的两个相邻元素和中最小的那个作为经过当前元素的最小路径和，每一层都重复以上判断，最终我们遍历最后一行列的元素，得到最小的路径和。部分测试用例有些问题，并不符合题目所说的三角形排列，故我们需要注意遍历每一行元素时，要根据每一行实际的长度进行遍历操作。
Java题解如下
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param cows int整型二维数组
* @return int整型
*/
public int minimumTotal (int[][] cows) {
// write code here
int n = cows.length;
int[][] dp = new int[n][n];
dp[0][0] = cows[0][0];
for(int i = 1; i < n; i++) {
dp[i][0] = dp[i - 1][0] + cows[i][0];
dp[i][cows[i].length - 1] = dp[i - 1][i - 1] + cows[i][cows[i].length - 1];
for(int j = 1; j < cows[i].length - 1; j++) {
dp[i][j] = cows[i][j] + Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
}
}
int min = Integer.MAX_VALUE;
for(int i = 0; i < cows[n - 1].length; i++) {
min = Math.min(min, dp[n - 1][i]);
}
return min;
}
}
投递阿里巴巴集团等公司10个岗位 >
查看21道真题和解析
一到周日晚上就处于一种啥也不想干提前开始焦虑的状态，每周一都完全起不来，但是还是要唯唯诺诺的爬到公司，不想上班不想上班不想上班
