Java 动态规划算法——硬币找零问题实例分析

简介

硬币找零问题是一类非常经典的问题，主要是如何计算出需要多少硬币才能凑够给定的金额。动态规划是解决硬币找零问题的一种常用算法。本文将介绍动态规划算法的工作原理及其在硬币找零问题中的应用。

动态规划算法

动态规划算法（Dynamic Programming）是一种解决问题的思想，它将问题拆分成若干个子问题，并为每个子问题找到最优解，从而最终得到原问题的最优解。它可以大大提高计算效率，是很多优化问题都采用的算法思路。

动态规划算法分以下几个步骤：

1. 定义子问题：明确选择哪些子问题，这些子问题共同构成原问题的解。
2. 定义状态方程：找出原问题与子问题之间的状态转移方程。
3. 初始化状态：将初始状态赋给原问题和子问题。
4. 递推求解：依次求解所有状态，最终得到原问题的解。

硬币找零问题

硬币找零问题是动态规划算法中的一种经典问题。假设你有一些、五元、十元和二十元的硬币，现在你需要准备15元的钱，那么如何最小化硬币的个数呢？

这个问题可以通过动态规划算法来解决。

首先需要定义子问题和状态方程：

定义子问题：对于金额n的硬币找零问题，设f(n)为将n元钱找零所需最小硬币数量。

定义状态方程：对于硬币面值d1、d2、……、dk，有转移方程f(i)=min{f(i-di)+1}，其中i表示目标金额，di表示第i枚硬币的面值，f(i-di)表示剩下的钱的金额，1即为所选的硬币数量。

初始化状态：f(0)=0，即不需要硬币即可找零。

递推求解：依次求解f(1)、f(2)、……、f(15)。

例如，对于15元的找零问题，可以按照下面的流程进行计算：

• f(0)=0，不需要找零。
• 当i=1时，最小硬币数量为f(1)=min{f(1-1)+1}=f(0)+1=1
• 当i=2时，最小硬币数量为f(2)=min{f(2-1)+1,f(2-2)+1}=f(1)+1=2
• 当i=3时，最小硬币数量为f(3)=min{f(3-1)+1,f(3-2)+1}=f(2)+1=3
• 当i=4时，最小硬币数量为f(4)=min{f(4-1)+1,f(4-2)+1,f(4-5)+1}=f(3)+1=4
• ……
• 当i=15时，最小硬币数量为f(15)=min{f(15-1)+1,f(15-5)+1}=f(14)+1=4

因此，需要至少4个硬币才能凑够15元。

Java实现

下面是Java实现硬币找零问题的代码示例：

public class CoinChange {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) return 0;
        int[] dp = new int[amount + 1];
        int sum = 0;
        while (++sum <= amount) {
            int min = -1;
            for (int coin : coins) {
                if (sum >= coin && dp[sum - coin] != -1) {
                    int temp = dp[sum - coin] + 1;
                    min = min < 0 ? temp : (temp < min ? temp : min);
                }
            }
            dp[sum] = min;
        }
        return dp[amount];
    }
}

示例说明

示例1

输入：coins = [1, 5, 10, 20], amount = 15

输出：4

解释：需要至少4个硬币才能凑够15元，即返回4。

示例2

输入：coins = [2], amount = 3

输出：-1

解释：无法凑够3元，因此返回-1。

结论

动态规划算法是解决硬币找零问题的一种常用算法。通过定义子问题和状态方程，实现了对硬币找零问题的求解。在实际编程过程中，通过Java语言的实现，更加深入地理解了动态规划算法的工作原理和运用场景。