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

贪心策略是什么

顾眼前

遵循某种规律，不断（贪心地）选取当前最优的策略，最终找到最优解
难点：当前最优未必整体最优
下面看简单例题

硬币问题

有1元,5元,10元,50元,100元,500元的硬币各c1,c5,c10,c50,c100,c500枚.
现在要用这些硬币来支付A元,最少需要多少枚硬币?
假定本题至少存在一种支付方案.

0≤ci≤10^9
0≤A≤10^9

输入说明:

第一行有六个数字,分别代表从小到大6种面值的硬币的个数
第二行为A,代表需支付的A元

输入

3 2 1 3 0 2
620

输出

6

说明:1500+250+110+25,共6枚

代码

当然也可以用循环 ，这里用递归
能用最大面值用多少 剩下的其余硬币组合
然后 求出 最小的需要的面值 就是 min(count[cur], maxGeshu); 这样就不会超过限定的面值 count[cur]
递归注意点就是 最后一个面值是1 所以 币值=面值 这是 一定的

package BlueCup.Eight_DP_greed;

import java.util.Scanner;

import static java.lang.Math.min;

public class 贪心硬币问题 {
    static int[] count;

    static int[] coin = {1, 5, 10, 50, 100, 500};

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        count = new int[6];
        for (int i = 0; i < 6; i++) {
            count[i] = cin.nextInt();
        }
        int value = cin.nextInt();
        int ans = f(value, 5);
        System.out.println(ans);
    }

    private static int f(int value, int cur) {
        if (value <= 0) return 0;//提前凑够了
        if (cur == 0) return value;//面值是1
        int maxGeshu = value / coin[cur];//需要
        int t = min(count[cur], maxGeshu);// 我有的和我需要的 选出最小的 去换
        return t + f(value - t * coin[cur], cur - 1);
    }
}