[数据结构与算法]java leetcode之[动态规划 中等]120. 三角形最小路径和

题目的链接在这里：https://leetcode-cn.com/problems/triangle/

题目大意

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

一、示意图

二、解题思路

动态规划

动态规划

代码如下：

class Solution {
 public int minimumTotal(List<List<Integer>> triangle) {
       //还有个边界需要处理
        if(triangle.size()==1){
            return triangle.get(0).get(0);
        }
        //三角形找出 自顶向下的最小路径之和 每一步只能移动到和他相邻的位置 也就是下一层的i的位置和i+1位置
        //这个怎么使用动态规划呢  dp[i]表示第i层的最小路径和 我感觉应该是 dp[i][j] 找最后一层 达到这个目的地的最小值
        int[][] dp=new int[triangle.size()][triangle.size()];
       // System.out.println("triangle = " + triangle.size());
        //第一层只可能是 一个
        dp[0][0]=triangle.get(0).get(0);
       // System.out.println("dp[0][0] = " + dp[0][0]);
        int res=100000;
        //然后就开始继续判断
        for(int i=1;i<dp.length;i++){
            //等到下面一层 有两个需要更新的地方
            for(int j=0;j<=i;j++){
                //j这位置 只可能是从他上一层的j和j-1的位置来找到
                if(j<1){
                    //说明上一层只有一个 那就直接上一层 加上这个对应位置的值
                    dp[i][j]=dp[i-1][j]+triangle.get(i).get(j);
                }
                //因为这数组都是空数组 还需要判断右边 不是最右边的
                 if(j>=1&&j<i){
                    //那就需要判断一下他上面那个 哪一个比较小了
                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+triangle.get(i).get(j);
                }
                 if(j==i){
                     //说明是这一层的最后一个 理论上来说 只能是上一层的j-1个
                     dp[i][j]=dp[i-1][j-1]+triangle.get(i).get(j);
                 }
                //然后这里判断一下最后一层里的最小值
                if(i==dp.length-1){
                    //说明是最底下一层
                    res=Math.min(res,dp[i][j]);
                }
               // System.out.println("dp[i][j] = " + dp[i][j]);
            }

        }
        return res;
    }

}