动态规划找零钱java

动态规划是一种算法思想，常用于解决涉及最优决策的问题，比如找零钱问题。在Java中，我们可以利用动态规划来设计一个程序来确定最小的硬币组合给定一定的金额。例如，经典的“硬币找零”问题可以描述为：

假设有一系列不同面额的硬币（如：1元、5角、1角），你需要找零一定金额。目标是最小化硬币的数量。

以下是基本的Java代码实现：

import java.util.Arrays;

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        // 初始化一个长度等于amount+1的数组dp，表示从0到amount所需的硬币数量
        int[] dp = new int[amount + 1];
        
        // 初始化所有值为无穷大，除了dp[0]设为0（不需要任何硬币找零0元）
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            // 遍历每种硬币
            for (int coin : coins) {
                // 如果当前硬币面额小于剩余金额，我们可以在找到零钱的数量上加一
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); // 更新最小硬币数量
                }
            }
        }
        
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; // 返回结果，若找不到解则返回-1
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10};
        int amount = 12;
        System.out.println(coinChange(coins, amount)); // 输出: 3 (需要3枚硬币，1枚10元，1枚5元，1枚1元)
    }
}