518. 零錢兌換 II （dp）

難度中等637

給你一個整數數組 <code>coins</code> 表示不同面額的硬币，另給一個整數 <code>amount</code> 表示總金額。

請你計算并傳回可以湊成總金額的硬币組合數。如果任何硬币組合都無法湊出總金額，傳回 <code>0</code> 。

假設每一種面額的硬币有無限個。 

題目資料保證結果符合 32 位帶符号整數。

示例 1：

示例 2：

示例 3：

提示：

<code>1 &lt;= coins.length &lt;= 300</code>

<code>1 &lt;= coins[i] &lt;= 5000</code>

<code>coins</code> 中的所有值 互不相同

<code>0 &lt;= amount &lt;= 5000</code>

<code>dp[i][j]</code> 的定義如下：

若隻使用前 <code>i</code> 個物品（可以重複使用），當背包容量為 <code>j</code> 時，有 <code>dp[i][j]</code> 種方法可以裝滿背包。

換句話說，翻譯回我們題目的意思就是：

若隻使用 <code>coins</code> 中的前 <code>i</code> 個硬币的面值，若想湊出金額 <code>j</code>，有 <code>dp[i][j]</code> 種湊法。

經過以上的定義，可以得到：

base case 為 <code>dp[0][..] = 0， dp[..][0] = 1</code>。因為如果不使用任何硬币面值，就無法湊出任何金額；如果湊出的目标金額為 0，那麼“無為而治”就是唯一的一種湊法。