题解 | #兑换零钱(一)# 完全背包变形 [P0]

完全背包变形
dp[i][v]: 用前i个硬币组合出价值v所需的最少硬币数
dp[0][0]=1, dp[0][v]=0 for v>0.
dp[i][v] = Min {
  (a) dp[i-1][v],      // 不用i硬币
  (b) dp[i][v-arr[i]]  // 用i硬币
}

完全与01背包的核心区别是
  - 01背包不能dirty write (一个硬币只能使用0或1次)， 
    i.e. (b)选项为 dp[i-1][v-arr[i]]
  - 完全背包就是要dirty write (一个硬币可以使用多次)
    i.e. (b)选项为 dp[i][v-arr[i]]

import java.util.*;

public class Solution {
  
    // 完全背包变形
    public int minMoney (int[] arr, int aim) {
      int[] mem = new int[aim+1];
      // 这里如果用Integer.MAX_VALUE，15行会overflow.
      // 因为 aim <= 5000, 所以结果不可能大于5000.
      Arrays.fill(mem, 5001);
      mem[0] = 0;  // {0, 5001, 5001 ... ... 5001}
      
      for (int i = 0; i < arr.length; i++) {
        for (int x = arr[i]; x <= aim; x++) {
          mem[x] = Math.min(mem[x], mem[x-arr[i]]+1);
        }
      }
      
      return mem[aim] == 5001 ? -1 : mem[aim];
    }
}