题目

类型：动态规划
image.png

解题思路

动态规划
https://leetcode.cn/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/

代码

  1. class Solution {
  2.    public int coinChange(int[] coins, int amount) {
  3.         if (amount < 0){
  4.             return -1;
  5.         }
  6.         int[] dp = new int[amount + 1];
  7.         Arrays.fill(dp, amount + 1);
  8.         // base case
  9.         dp[0] = 0;
  10.         // 外层 for 循环在遍历所有状态的所有取值
  11.         for (int i = 0; i < dp.length; i++) {
  12.             // 内层 for 循环在求所有选择的最小值
  13.             for (int coin : coins) {
  14.                 // 子问题无解，跳过
  15.                 if (i - coin < 0) {
  16.                     continue;
  17.                 }
  18.                 dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
  19.             }
  20.         }
  21.         return (dp[amount] == amount + 1) ? -1 : dp[amount];
  22.     }
  23. }