java 动态规划（三角形最短路径和）

刺骨的言语ヽ痛彻心扉 2022-11-21 11:20 199阅读 0赞

--------------------

### java 动态规划（三角形最短路径和） ###

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**三角形最短路径和**

**问题描述**

给定一个三角形，找出自顶向下的最小路径和
    每一步只能移动到下一行中相邻的结点上(相邻节点：索引相同、索引+1)
    
    
    示例：
    [
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]
    
    最短路径和：11 (2+3+5+1)

**动态规划求解：自底向上，相邻元素取较小者，替换上层对应元素，最终返回顶层元素**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70 2][]

## ##

### \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* ###

**示例**

public class MyTest4 {
    
        public static List<List<Integer>> generate(){
            List<List<Integer>> lists=new ArrayList<>();
    
            List<Integer> list=new ArrayList<>();
            list.add(2);
    
            List<Integer> list2=new ArrayList<>();
            list2.add(3);
            list2.add(4);
    
            List<Integer> list3=new ArrayList<>();
            list3.add(6);
            list3.add(5);
            list3.add(7);
    
            List<Integer> list4=new ArrayList<>();
            list4.add(4);
            list4.add(1);
            list4.add(8);
            list4.add(3);
    
            lists.add(list);
            lists.add(list2);
            lists.add(list3);
            lists.add(list4);
    
            return lists;
        }
    
        public static int fun(List<List<Integer>> lists){
            int size=lists.size();
    
            if (size==0){
                return 0;
            }
    
            if (size==1){
                return lists.get(0).get(0);
            }
    
            for (int i=size-1;i>0;i--){
                List<Integer> curList=lists.get(i);
                List<Integer> preList=lists.get(i-1);
    
                for (int j=0;j<curList.size()-1;j++){
                    int cur=curList.get(j);
                    int next=curList.get(j+1);
    
                    int value=preList.get(j);
                    preList.set(j,Math.min(cur,next)+value);
                }
            }
    
            return lists.get(0).get(0);
        }
    
        public static void main(String[] args){
            System.out.println("最短路径和为："+fun(generate()));
        }
    }

**控制台输出**

最短路径和为：11

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70]: /images/20221120/d379dc64958443f48f1871b1f1318298.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/b682a949f64b4a51ae8c6f0493d36b5c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzMTYyNQ_size_16_color_FFFFFF_t_70 2]: /images/20221120/68c078ff11e14694a5ba4442ca29b597.png