给定一个三角形 triangle ，找出自上而下的最小路径和。

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

示例 1：

输入：triangle = [2]，[3，4]，[6，5，7]，[4，1，8，3]
输出：11
说明:如下图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径是 11（即，2 3 5 1 = 11）。

示例 2：

输入：triangle = [[-10]]
输出：-10

进阶：

只能用 O(n) 的额外空间（n 解决三角形的总行数吗？

import java.util.*;  class Solution { 
             public int minimumTotal(List<List<Integer>> triangle) { 
                 int[] dp = new int[triangle.size()];         int ans = 0;         dp[0] = triangle.get(0).get(0);         int temp, prev = 0, cur;         for (int i = 1; i < triangle.size(); i ) { 
                     for (int j = 0; j < triangle.get(i).size(); j++) { 
        
                temp = triangle.get(i).get(j);
                cur = dp[j];
                if (j == 0)
                    dp[j] = cur + temp;
                else if (j == triangle.get(i).size() - 1)
                    dp[j] = prev + temp;
                else
                    dp[j] = Math.min(prev, cur) + temp;
                prev = cur;
            }
        }
        for (int i = 1; i < dp.length; i++) { 
        
            if (dp[ans] > dp[i])
                ans = i;
        }
        return dp[ans];
    }

    public static void main(String[] args) { 
        
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        List<Integer> list1 = new ArrayList<Integer>();
        list1.add(2);

        List<Integer> list2 = new ArrayList<Integer>();
        list2.add(3);
        list2.add(4);

        List<Integer> list3 = new ArrayList<Integer>();
        list3.add(6);
        list3.add(5);
        list3.add(7);

        List<Integer> list4 = new ArrayList<Integer>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);

        triangle.add(list1);
        triangle.add(list2);
        triangle.add(list3);
        triangle.add(list4);

        Solution solution = new Solution();
        int total_min = solution.minimumTotal(triangle);
        System.out.println(total_min);
    }
}

二战后的某一天，N个日本人来到了一个山洞休息，为了派出一个日本人去外面充满危险的丛林中采摘食物，他们设置如下游戏产生外出采摘的人：

• 1、首先，所有参加游戏的日本人按顺序编号为1、2、3…N；
• 2、接下来每个日本人心里产生一个数字，这个数字称为序号为 N的人的密码P；
• 3、所有参加游戏的人按照编号站成一个圈，长老为游戏设置初始密码K，从编号为 1的人开始报数，报到 K的人退出队伍，然后将自己心中的密码P说出来，由下一个人继续从 1开始报数，报到P的人退出队伍，以此类推；
• 4、当队伍中剩下一个人的时候，这个人就是今天要出去采摘的日本人，他可能回不来了！ 请各位同学设计程序并使用Java语言实现改程序，在用户输入了人数N、每个人的密码P和初始密码K的情况下，自动完成上面的选择过程，输出先后离开队伍的人的序号序列，最后输出要去采摘的日本人，输出他的编号。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class JosephCircle { 
        
    public int newJoseph(int n, int[] p, int k) { 
        
        List<Integer> num = new ArrayList<Integer>();
        for (int i = 0; i < n; i++)
            num.add(i);
        int t = k, index = 0;
        for (int i = 0; i < n - 1; i++) { 
        
            index = (index + t) % num.size();
            num.remove(index);
            t = p[index];
            if (index == num.size())
                index = 0;
        }
        return num.get(0) + 1;
    }

    public int oldJoseph(int n, int k) { 
        
        int w = 0;
        for (int i = 2; i <= n; i++) { 
        
            w = (w + k) % i;
        }
        return w;
    }

    public static void main(String[] args) { 
        
        JosephCircle jc = new JosephCircle();
        Scanner scan = new Scanner(System.in);
        int n, k;
        int[] p = new int[100];
        System.out.print("Enter N = ");
        n = scan.nextInt();
        System.out.print("Enter P[] = ");
        for (int i = 0; i < n; i++) { 
        
            p[i] = scan.nextInt();
        }
        System.out.print("Enter K = ");
        k = scan.nextInt();
        System.out.println();
        System.out.println("Survivor is No." + jc.newJoseph(n, p, k));
    }
}