https://leetcode-cn.com/problems/coin-change/submissions/

动态规划

  • dp[ i ][ j ]

    • arr[ 0…i ]所有钱自由使用，能拼出 j 元的最小硬币个数

  • 初始化

image.png

  • 普遍位置怎么填？dp[ i ][ j ]
    • 0) 0张[ i ]钱， —> dp[ i - 1 ][ j ]
    • 1) 1张[ i ]钱， —> dp[ i - 1 ][ j - coins[ i ] ] + 1
    • 2) 2张[ i ]钱， —> dp[ i - 1 ][ j - coins[ i ] * 2 ] + 2
    • …) …..
    • k) k张[ i ]钱， —> dp[ i - 1 ][ j - coins[ i ] * k ] + k
  • 可以看出dp[i][j]有枚举行为——->斜率优化（观察自己临近的位置，看能不能把枚举行为省掉）

image.png
image.png
image.png

  2.     public int coinChange(int[] coins, int amount) {
  3.         if (coins == null || coins.length == 0 || amount == 0) {
  4.             return -1;
  5.         }
  6.         int N = coins.length;
  7.         int[][] dp = new int[N][amount + 1];
  8.         // dp[i][0] = 0 0列不需要填
  9.         // dp[0][1...] = arr[0]的整数倍，有张数，倍数，其他的格子-1（表示无方案）
  10.         for (int j = 1; j <= amount; j++) {
  11.             if (j % coins[0] != 0) {
  12.                 dp[0][j] = -1;
  13.             } else {
  14.                 dp[0][j] = j / coins[0];
  15.             }
  16.         }
  18.         for (int i = 1; i < N; i++) {
  19.             for (int j = 1; j <= amount; j++) {
  20.                 //dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]]);
  21.                 dp[i][j] = Integer.MAX_VALUE;
  22.                 if (dp[i - 1][j] != -1) {
  23.                     dp[i][j] = dp[i - 1][j];
  24.                 }
  25.                 if (j - coins[i] >= 0 && dp[i][j - coins[i]] != -1) {
  26.                     dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]]  + 1);
  27.                 }
  28.                 if (dp[i][j] == Integer.MAX_VALUE) {
  29.                     dp[i][j] = -1;
  30.                 }
  32.             }
  33.         }
  34.         return dp[N - 1][amount];
  35.     }