题解 | #三角形#

三角形

http://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7da

import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        /*//方法一:从上往下走,最后累积的值存在了triangle.get(size-1).get(j)对应的数组arr[size-1][j]中
        int size=triangle.size(); //定义行
        //三角形的列随着行变换
        if(triangle.isEmpty()||size==0){
            return 0;
        }
        int [][] everysum=new int[size][size];
        everysum[0][0]=triangle.get(0).get(0);
        for(int i=1;i<size;i++){
            for(int j=0;j<=i;j++){
                //累计往下加
                if(j==0){
                    //最左边一行的情况
                    everysum[i][j]=triangle.get(i).get(j)+everysum[i-1][j];
                }else if(j==i){
                    //最右边一行的情况
                    everysum[i][j]=triangle.get(i).get(j)+everysum[i-1][j-1];
                }else{
                    //非边界,即0<j<i
                    everysum[i][j]=triangle.get(i).get(j)+Math.min(everysum[i-1][j],everysum[i-1][j-1]);
                }
            }
        }
        //到这一步已经累计到最后一行了,最后一行所有元素中找最小的即可
        int minsum=everysum[size-1][0];
        for(int j=1;j<size;j++){
           minsum=Math.min(minsum,everysum[size-1][j]);
        }
        
        return minsum;*/
        //方法二:从下往上走,最后累积的值存在了triangle.get(0).get(0)对应的数组arr[0][0]中
        int size=triangle.size();//==行数==最大列数
        if(size==0||triangle.isEmpty()){
            return 0;
        }
        //新建二维数组,并且把最后一行赋值上
        int[][] array=new int[size][size];
        for(int j=0;j<size;j++){
            array[size-1][j]=triangle.get(size-1).get(j);
        }
        for(int i=size-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                array[i][j]=Math.min(array[i+1][j],array[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return array[0][0];
    }
}


全部评论

相关推荐

找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
06-25 09:33
厦门大学 Java
程序员饺子:现在日常估计没啥hc了,等到八月多估计就慢慢有了。双九✌🏻不用焦虑的
投递快手等公司7个岗位
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务