方法一:dp+memo
类似 添加链接描述
memo[i][j] 表示从 triangle[0][0]到triangle[i][j] 所经过的路经总和大小;
找到规律: 第triangle[i][j]
的结点 只会来自于 triangle[i-1][j-1]
和 triangle[i-1][j]
,将这两种取最小,再加上自己,就是 memo[i][j];
输出的结果没有确定,最后一行有 j 个,需要在main中依次判断哪个最小!
class Solution {
int[][] memo;
public int minimumTotal(List<List<Integer>> triangle) {
int n=triangle.size();
int m=triangle.get(n-1).size();
memo=new int[n][m];
for(int[] k:memo){
Arrays.fill(k,666666);
}
int r=666666;
for(int j=0;j<m;j++){
r=Math.min(r, dp(triangle,n-1,j));
}
return r;
}
int dp(List<List<Integer>> triangle,int i,int j ){
//
if( i==0 && j==0){
return triangle.get(0).get(0);
}
// 越界, 返回特殊值
if(i<0 || j<0 || j>=triangle.get(i).size()){
return 666666;
}
// 重叠子问题
if(memo[i][j]!=666666){
return memo[i][j];
}
memo[i][j]=triangle.get(i).get(j) +
Math.min(dp(triangle,i-1,j-1), dp(triangle,i-1,j));
return memo[i][j];
}
}
方法二:dp
import java.util.*;
public class Solution {
public int maximumTotal (int[][] triangle) {
if(triangle==null || triangle.length==0){
return 0;
}
// 从下往上推!
int n=triangle.length;
int m=triangle[n-1].length;
int[][] dp=new int[n][m];
//dp 要累加!
for(int[] k:dp){
Arrays.fill(k,-1);
}
for(int j=n-1;j>=0;j--){ //最后一行赋给 dp[n-1][]
dp[n-1][j]=triangle[n-1][j];
}
// 从下往上,
for(int i=n-2;i>=0;i--){
for(int j=0;j<triangle[i].length;j++){
if(dp[i][j]!=-1){
continue;
}
dp[i][j]=triangle[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
}
}
return dp[0][0];
}
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/89176.html