动态规划和贪心算法都是一种递推算法，均用局部最优来推导全局最优，是对遍历解空间的一种优化。当问题具有最优子结构的时候可以用动态规划，而贪心是动态规划的特例。 贪心策略可以看做是DFS的剪枝。

贪心算法

1. 多人过河

多个人过河，只有一条船，一次最多坐两人，过河用时为划船用时最慢的那个人的用时，给出n个人的划船用时，求这n个人过河的最短用时。

• 思路
  • 1个人时，用时为这个人的划船用时
  • 2个人时，用时为划船用时多的那个人的用时
  • 3个人时，由于需要两个人先过去，再一个人划船回来，剩余两个人再过去，可以想到用时为三人用时之和。
  • 4个人时，情况复杂一些，加入耗时从小到大的四个人为a、b、c、d
    • 第一种方案，ab过去，a回来，ac过去，a回来，ad过去，用时2a+b+c+d
    • 第二种方案，ab过去，a回来，cd过去，b回来，ab过去 用时a+3b+d 两种方案比较，扣除相同的部分 a+c 2b 取耗时较短的方案。

比较4人时的两种过河方案，可以看成耗时最短的和次短的用什么样的方式耗时最长的和次长的过河，第一种可以看成是利用耗时最短的a送耗时最长的和次长的过河。 第二种方案可以看成 利用耗时最短的a和b将耗时最长的和次长的送过去。由于船一次只能坐两人，所以不存在其他方案会比这两个方案耗时少了。那么当人数超过三人时，可以递归的使用这个方法使得需要考虑的过河人数每次减2，降低问题的规模。

需要注意的是，用第二种方式时，优先考虑带过河的必须是耗时最长的和耗时次长的，因为耗时最长的和其他人过河必然使用最长耗时计数，将他和耗时次长的一起过河，避免耗时次长的纳入之后的计算, 所以应当对过河的人按耗时进行排序

@Test
public void t_多人过河() {
    int[] speed = {1,2,3,4};
    Arrays.sort(speed);
    int leftNum = speed.length;
    int totalTime = 0;
    while (leftNum>0){
        if (leftNum == 1){
            totalTime += speed[0];
            break;
        }else if (leftNum == 2){
            totalTime += speed[1];
            break;
        }else if (leftNum == 3){
            totalTime += speed[0] + speed[1] + speed[2];
            break;
        }else {
            //1，4出发，1返回，1,3出发，1返回
            int t1 = 2*speed[0]  + speed[leftNum-1] +speed[leftNum-2];
            //1,2出发，1返回，3,4出发，2返回
            int t2 = speed[0] + 2*speed[1] +speed[leftNum-2];
            leftNum -=2;
            totalTime += Math.min(t1,t2);
        }
    }
    System.out.println(totalTime);
}

动态规划

表现形式： 重叠子问题、最优子结构、dp方程

1. 01背包问题 找出状态转移方程：考虑第n个物品的选还是不选 选 第n个物品的重量+剩余空间下前n-1物品的选法 不选 对应空间下前n-1个物品的选法 所以每次考虑第i个物品时，需要计算所有剩余空间的情况，以便计算i+1的时候直接利用上一次的计算结果

背包容量为j时第i个物品的最优策略 dp[i][j] = Max( v[i]+dp[i-1][j-w[j]] , dp[i-1][j] )

2. 完全背包问题 即每一个物品都可以取任意次或不取 与01背包不同的是，对于第n个物品，需要考虑取1次，2次... 后的剩余空间留给前n-1个物品，然后从中选取价值最大的。 这里有一个可以优化的地方，当取1次当前物品后，剩余空间对于前n个物品的最优情况实际已经计算过了。 背包容量为j时第i个物品的最优策略 dp[i][j] = Max( v[i]+dp[i][j-w[j]] , dp[i-1][j] )