Readme

3592.Inverse-Coin-Change

这是一道非常有意思的“反向重构”的DP题。

首先，从题境上来看这类似一道经典的背包问题。给出一系列硬币面值coins可以无限重复使用，问有多少种构造方法能拼出面值n来？对于这个问题，我们有如下动态规划解法。特别注意最外层的循环是硬币面额

for (int c: coins)
  for (int i=c; i<=n; i++)
    dp[i] += dp[i-c];

状态转移的思想就是，每轮引入一种新的硬币面额c：遍历所有面值i，考察最后一个硬币是否使用c。如果不使用，那么dp[i]依然是前一轮的数值；如果使用c，那么就取决于dp[i-c]。

我们可以沿用同样的思路，来思考numWays（也就是dp）是怎么计算出来的

for (int c: coins) {
   if c 不存在
      continue;
   else if c 存在
      for (int i=c; i<=n; i++)
         dp[i] += dp[i-c];
}

那么如何判断c是否存在呢？突破点就是面额c的构造方法。如果numWays[c]等于前一轮（还没有引入面额c的时候）的dp[c]，那么就意味着面额c一定不存在。否则c的构造必然至少还能增加一种方法（即只使用一个c硬币）。反之，面额c必须存在，否则无法弥补这个差额。

当然，我们仅凭numWays[c]的分析来决定面额的种类还是比较片面的，它不能保证最终据此计算得到的dp都与所有的numsWays一致。所以我们还要再次校验一下。