编辑代码

public class CoinChange {
    public int coinChange(int[] coins, int target) {
        int[][] dp = new int[coins.length + 1][target + 1];
        // 初始化
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 0;
        }
        // 状态转移
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (coins[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                }
            }
        }

        return dp[coins.length][target] == Integer.MAX_VALUE ? -1 : dp[coins.length][target];
    }

    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();
        int[] coins = {1, 2, 5};
        int target = 11;
        int result = coinChange.coinChange(coins, target);
        System.out.println("（20052248田雨瑶）最少投币数：" + result);
    }
}