思路：类似于跳台阶（爬楼梯）问题。
爬楼梯问题的 target 在外层。
class Solution { /** * 思路； 转化为跳台阶问题 * 1. 状态的定义： dp[i] 表示到i台阶时的最小步数, 也即凑齐i需要的最少硬币数 * 2. 状态转移方程 dp[i] = min {dp[i-coins[j]} + 1 * 举例： [1,2,5] 11 * dp[i] = min{i-1, i-2, i-5} + 1 * dp[11] = min{dp[10],dp[9],dp[6]} + 1 */ public int coinChange(int[] coins, int amount) { // dp[i] 表示可以凑成总金额为 i 所需的最少硬币个数。 int[] dp = new int[amount + 1]; // 最多的硬币数就是全部使用面值1的硬币来换, amount+1是不可能达到的换取数量。 // 因为硬币面额最小为整数1，所以只要有解，最小硬币数必然小于amount+1 int max = amount + 1; Arrays.fill(dp, max); dp[0] = 0; // 注意要单独初始化 for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (i - coins[j] >= 0) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } }