Java动态规划实现硬币找零问题：算法原理与代码解析

问题描述

假设我们拥有无限数量的几种硬币，面值分别为 [1, 3, 5]。目标是找出能够组成某个目标数目（例如 k）的找零所使用的最少硬币数。

• 面值2的最少硬币数为2：(1, 1)
• 面值4的最少硬币数为2：(1, 3)
• 面值11的最少硬币数为3：(5, 5, 1) 或 (5, 3, 3)

算法分析与状态定义

动态规划的基本思想是将待求解问题分解成若干个子问题，先求解子问题，并将这些子问题的解保存起来（通常保存在数组中）。如果以后在求解较大子问题时需要用到这些子问题的解，就可以直接取出而免去重复运算。

设不同的硬币面值为数组 coin[0, ..., n-1]，求面值 k 的最少硬币数 count(k)，其递归关系如下：

count(k) = min(count(k - coin[0]), ..., count(k - coin[n - 1])) + 1;

该公式成立的前提条件是 k - coin[i] >= 0 且 k - coin[i] < k。由于要求解 count(k) 时必须已知所有 i < k 的 count(i)，这涉及到状态的逐步回溯与填充。

为了清晰展示过程，我们可以创建一个二维矩阵 matrix[k + 1][coin.length + 1]：

1. 最后一列 matrix[i][coin.length] 用于保存面值 i 的最少硬币总数。
2. 前面的列 matrix[i][j] 表示使用前 j 种硬币面值时，凑成金额 i 所需的最少硬币数。
3. 初始化时，使 matrix[0][j] 全部为 0（金额为0不需要硬币）。

第1步：理解状态转移过程

以下是部分状态的推导示意（格式为：k | coin 1 3 5 min）：

* k|coin 1  3  5  min
 * 0    0  0  0  0
 * 1    1  0  0  1
 * 2    2  0  0  2
 * 3    3  1  0  3, 1  // 面值3可以用(1,1,1)共3个，或用(3)共1个，取min=1
 * 4    2  2  0  2, 2  // (1,3)或(1,1,1,1)，min=2
 * 5    3  3  1  3, 3, 1 // min=1
 * 6    2  2  2  2, 2, 2

第2步：Java代码实现

基于上述逻辑，具体的Java实现代码如下。该方法采用回溯法结合动态规划的填表方式：

public static int backTrackingCoin(int[] coins, int k) {
    // 边界条件检查：硬币数组为空或目标金额小于1
    if (coins == null || coins.length == 0 || k < 1) {
        return 0;
    }
    
    // 创建状态矩阵：行数为k+1（包含金额0到k），列数为硬币种类数+1
    int[][] matrix = new int[k + 1][coins.length + 1];
    
    // 外层循环遍历所有目标金额 i
    for (int i = 1; i <= k; i++) {
        // 内层循环遍历每种硬币 j
        for (int j = 0; j < coins.length; j++) {
            int preK = i - coins[j];
            // 只有当剩余金额不小于0时，才能进行回溯查找
            if (preK > -1) {
                // 尝试使用当前硬币 j，所需数量为 "凑齐preK的最少数量" + 1
                matrix[i][j] = matrix[preK][coins.length] + 1;
                
                // 如果这是第一次计算该金额i的最优解，或者比之前的记录更优，则更新最后一列
                if (matrix[i][coins.length] == 0 || matrix[i][j] < matrix[i][coins.length]) {
                    matrix[i][coins.length] = matrix[i][j];
                }
            }
        }
    }
    // 返回凑齐金额k所需的最少硬币数
    return matrix[k][coins.length];
}

测试与验证

上述代码经过标准测试用例验证，能够正确处理各种硬币组合情况。通过观察 matrix 表中最后一列的变化，可以清晰地看到随着目标金额增加，最少硬币数量的递增规律，体现了动态规划自底向上求解的优势。

以上就是Java动态规划实现硬币找零问题的详细内容，更多关于Java 硬币找零算法优化的资料请关注本站其它相关文章！