题解 | JAVA #兑换零钱(二)# 完全背包变形 [P0-T2]

完全背包问题的变形。

input: 5,[1,2,4,5]

vi  dp[0  1  2  3  4  5]
0      1  0  0  0  0  0
1      1  1  1  1  1  1 
2      1  1  2  2  3  3 
4      1  1  2  2  4  4
5      1  1  2  2  4  5

时间: O(NT)
空间: O(T)

import java.util.*;

public class Solution {
  // dp[i][s]: ways of using fist i coins to sum to s
  //   = dp[i-1][s] + dp[i][s-num[i]]
  // basecase: dp[0][0] = 1, dp[0][!0] = 0
  public int change (int target, int[] nums) {
    int[] dp = new int[target+1];
    dp[0] = 1; // dp[0][0]
    for (int i = 0; i < nums.length; i++) {
      // dp[i][s] = dp[i-1][s] (i.e. no change) for s < nums[i]
      for (int s = nums[i]; s <= target; s++) {
        dp[s] = dp[s] + dp[s-nums[i]];
      }
    }
    
    return dp[target];
  }
}