triangle(三角形最短路径)

1.题目

给定一个三角形，从上到下找到最小路径和。 您可以移动到下一行的相邻数字的每一步。
例如，给出以下三角形
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
从顶部到底部的最小路径和为11（即，2 + 3 + 5 + 1 = 11）。

2.分析思路

     (1)思路一：动态规划。
        给定一个三角形，找出从顶到底的最小路径和，每一步可以从上一行移动到下一行相邻的数字。
[                   
       [2],                 [2],              
      [3,4],              [3, 4],              [2],
     [6,5,7],      ==>   [7, 6, 10]     ==>  [9, 10]   ==>     [11]
    [4,1,8,3]
 ]
 （2）思路二：递归（深度遍历）。
          整个三角形可以看做一个二叉树，每一层的每个节点都有两条路径，深度优先遍历找出最短路径。

3.代码实现

（1）动态规划参考牛客网答案

import java.util.*;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        list.addAll(triangle);//为了不改变原来的三角形
        for (int i = list.size() - 2; i >= 0; i --) {
            for (int j = 0; j < list.get(i + 1).size() - 1; j ++) {
                int min = Math.min(list.get(i + 1).get(j), list.get(i + 1).get(j + 1));
                list.get(i).set(j, list.get(i).get(j) + min);
            }
        }
        return list.get(0).get(0);
    }
}

（2）递归（深度遍历）

import java.util.*;
public class Solution {

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if(triangle==null || triangle.size()==0) return 0;
        int n=triangle.size()-1;
        return minimumTotal(triangle,0,0,n);
    }

    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle,int index1,int index2,int len){
        if(index1>len || index2>index1+1) return 0;
        int base=triangle.get(index1).get(index2);
        return base+Math.min(minimumTotal(triangle,index1+1,index2,len),minimumTotal(triangle,index1+1,index2+1,len));
    }

}

题目来自牛客网leetcode