假设存在2，3，5元三种硬币，给定一定数量的钱，需要换成这三种硬币，并且使用最少的硬币数量
这个问题的本质是子问题最优解，由子问题最优解上构造出来的更高级的解也是最优解
假设你需要找出2的找钱方案，可以直接取得最优解1，找出3，可以直接找出最优解1，找出4，此时问题似乎有些麻烦，但是如果4是可以被找出的话，那么它一定由2，3，5组成，也就是说由2，3，5组成4的最后一步必然是2，3，5其中一个，那么我们就可以循环这三种硬币，4-2得2，2有最优解1，4-3得1，没有解，4-5小于0也没有，那么答案显而易见，就是2的最优解+1，也就是2就是最优解，那么任何数都可以通过这种方法来获得最优解，只要它是有解的
代码如下

public class App {
    @Test
    public void Test1(){
        //这里设置硬币种类
        int[] coins =new int[]{2,3,5};
        int min=change(coins,10);
        System.out.println(min);
    }
    public int change(int[] coins, int num) {
        //如果为0，无解
        if (num == 0) return 0;
        //默认创建一个能容纳5个零钱的数组，这里是为了和下面配合所以默认要5个大小，因为从1开始需要6的大小
        //这里代表每个数字的可能性，所以不从0开始而是1
        int[] optimal = new int[6];
        //这里同上
        if (num > 6) optimal = new int[num + 1];
        //给所有位置填上-1代表还没有解
        Arrays.fill(optimal, -1);
        //循环给硬币种类填上1，因为这几个数字只有唯一解
        //因为这里需要给2，3，5默认情况，所以数组直接大于5，这也就是为什么上面要设置6的大小
        for (int coin : coins) optimal[coin] = 1;
        //从1开始循环到21，也就是所有情况
        for (int v = 1; v <= num; v++) {
            //如果v个硬币已经有解的话，就跳出这次循环
            if (optimal[v] != -1) continue;
            //如果v个硬币暂时没给出解时，循环三种硬币种类
            for (int coin : coins) {
                //如果第v种减去2，3，5中任何一种小于0了或者结果暂时无解，就跳出这次循环
                //存在的情况例如，6-5，此时为1，但是1无解
                if (v - coin < 0 || optimal[v - coin] == -1) continue;
                //如果v个硬币情况未标注解或者v-2，3，5中任何一个有解并且比当前解更优
                //并且上面那个if已经规避了v-2，3，5会出现无解的情况，所以尽管把当前的解填为当前情况的最优解
                if (optimal[v] == -1 || optimal[v - coin] + 1 < optimal[v])
                    //把v个硬币的最优解填为v-2，3，5情况里的最优解+1步
                    optimal[v] = optimal[v - coin] + 1;
            }
        }
        //返回数组内v种硬币的最优解
        return optimal[num];
    }
}

代码来自于刘铁猛老师的算法之禅：递推与递归
这篇博客也是来自于我看过书之后的理解和思考