最优解问题：找零钱

问题

问题描述

给定 n 种不同面值的硬币，有一个总金额 k，计算出最少需要几枚硬币凑出这个金额k ？每种硬币的个数不限。如果没有任何一种硬币组合能组成总金额时，返回 -1。

示例：

输入：c[0]=1, c[1]=2, c[2]=5, k=12

输出：3 

解释：12 = 5 + 5 + 2

动态规划思路

初始化状态：由于动态规划是根据已经计算好的子问题推广到更大问题上去的，因此我们需要一个“原点”作为计算的开端；
状态：找出子问题与原问题之间会发生变化的变量，这个变量就是状态转移方程中的参数；
决策：改变状态，让状态不断逼近初始化状态的操作。这个决策，就是状态转移方程状态转移的方向。

分析

最少硬币数，显然也是一个求最值的问题。

可以从 0-k 求出每种面额下的最少硬币数，直到求出 k。

按动态规划思路来：

初始化状态

总额为0对应的硬币数也是0，总额>0 的 i 对应的硬币数最多就是 i + 1 （最小面值为1，所以最大就是 i，取一个不可能的最大值 i + 1 枚硬币）
状态参数

动态的总额 + 硬币数。寻找子问题发生变化的量。
决策

总额对应的最少硬币数 = min(x, (总额-该硬币面值) + 1) 。让状态不断逼近初始化状态的操作。
备忘录

dp[i] – i 表示总额，值就是硬币数

代码

public class Coin {
    public static void main(String[] args) {
        // 硬币面值
        int[] values = {1, 2, 5};
        // 总值
        int total = 12;

        int minCounts = getMinCounts(total, values);

        System.out.println(minCounts);

    }

    static int getMinCounts(int k, int[] values) {
        // 创建备忘录 表示该总值 i 下的硬币最少个数
        int[] memo = new int[k + 1];
        // 初始化状态
        memo[0] = 0;
        // 初始化 memo[>0] k+1 表示最大硬币个数+1
        for (int i = 1; i < k + 1; i++) {
            memo[i] = k + 1;
        }

        for (int i = 1; i < k + 1; i++) {
            for (int coin : values) {
                if (i - coin < 0) {
                    continue;
                }
                // 做出决策
                // i - 当前coin
                memo[i] = Math.min(memo[i], memo[i - coin] + 1);
            }
        }

        return memo[k] == k + 1 ? -1 : memo[k];
    }

}

算法