【重点】【DP】322.零钱兑换

题目

法1：动态规划

// 时间复杂度：O(kN)
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, amount + 1);dp[0] = 0;for (int i = 1; i < dp.length; ++i) {for (int coin : coins) {if (i - coin >= 0) {dp[i] = Math.min(dp[i], 1 + dp[i - coin]); // 1就是本次枚举的coin}}}return (dp[amount] == amount + 1) ? -1 : dp[amount];}
}