题目：
在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。
输入：
有序数组（自定为有序，实际任意，数组内的数字代表对应索引过桥的时长）、数组长度
输出：
累加最短的时间
实现：
public class 自底向上实现线性模型 { private static int minTime(int p[],int n){ int opt[] = new int[n+1]; for (int i = 0; i < n; i++) { opt[i] = p[i]; } int minTime = 0; // 没有人的情况下 if (n == 0) return 0; // 有一个人时，返回这个人的时间 if (n == 1) return p[n-1]; // 有两个人时，返回用时较多的人的时间 if (n == 2) return Math.max(p[n-1],p[n-2]); /** * 人数多于2时，采用动态规划的思想，将问题拆分 * 假设河的这一侧还剩一人，则派遣最快的人往返 * 假设河的这一侧还剩二人，先派遣花费时间最少的人过来，待这两人走后，花费时间此少的人过来携带最少的人一同回去 */ for (int i = 2; i < n; i++) { opt[i] = Math.min(opt[i-1]+p[0]+p[i],opt[i-2]+p[0]+p[i]+2*p[1]); minTime = opt[i]; } return minTime; } public static void main(String[] args) { System.out.println(minTime(new int[]{1,2,5,10,11},5)); } }
原文：https://www.cnblogs.com/zbb2161228/p/10549139.html