用java写一个用动态规划思想解决硬币选择问题的代码

硬币选择问题是一个经典的动态规划问题，通常描述为：给定一个总金额和不同面额的硬币，要求使用最少的硬币数量凑成这个金额。这里提供一个简单的Java实现示例：

public class CoinChangeProblem {

    // 动态规划解决硬币选择问题
    public int coinChange(int[] coins, int amount) {
        // dp[i]表示组成金额i所需的最小硬币数
        int[] dp = new int[amount + 1];
        // 初始化dp数组为一个大数，表示不可达的情况
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        // 面额为0的硬币有一个，不需要其他硬币即可组成
        dp[0] = 0;

        // 动态规划填表
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        // 如果dp[amount]还是初始值，则表示无法凑出该金额
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        CoinChangeProblem solution = new CoinChangeProblem();
        int[] coins = {1, 2, 5};  // 硬币的面额
        int amount = 11;          // 目标金额
        int result = solution.coinChange(coins, amount);
        System.out.println("最少硬币数为: " + result);
    }
}

上述代码中，`coinChange`函数使用动态规划算法来计算组成给定金额所需的最少硬币数。它通过维护一个数组`dp`来记录达到每个金额所需的最小硬币数，并且对于每种面额的硬币，更新`dp`数组的对应值。