主題
題目連結：
題目意譯：
現在有一個考試，其有 n 種問題。你被給定一整數 target 以及一個索引值從 0 開始的二維整數陣列 types，其中 types[i] = [counti, marksi] 代表著考試中第 i 種類型的問題有 counti 道，而每一道值 marksi 分。
回傳你在本次測驗可以得到恰好 target 分的方法數。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
注意到同一種的問題彼此是「無法分辨差異的」。
例如說，如果現在某一種問題有 3 道，則解其中的第 1 道和第 2 道，與解其中的第 1 、 3 道以及解第 2 、 3 道是一樣的。
限制：
1 ≦ target ≦ 1000
n == types.length
1 ≦ n ≦ 50
types[i].length == 2
1 ≦ counti, marksi ≦ 50
範例測資：
範例 1：
輸入： target = 6, types = [[6,1],[3,2],[2,3]]
輸出： 7
解釋： 你可以藉由以下七種方式得到 6 分：
- 解 6 道第 0 種問題：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解 4 道第 0 種和 1 道第 1 種問題：1 + 1 + 1 + 1 + 2 = 6
- 解 2 道第 0 種和 2 道第 1 種問題：1 + 1 + 2 + 2 = 6
- 解 3 道第 0 種和 1 道第 2 種問題：1 + 1 + 1 + 3 = 6
- 解 1 道第 0 種、 1 道第 1 種和 1 道第 1 種問題：1 + 2 + 3 = 6
- 解 3 道第 1 種問題：2 + 2 + 2 = 6
- 解 2 道第 2 種問題：3 + 3 = 6
範例 2：
輸入： target = 5, types = [[50,1],[50,2],[50,5]]
輸出： 4
解釋： 你可以藉由以下四種方式得到 5 分：
- 解 5 道第 0 種問題：1 + 1 + 1 + 1 + 1 = 5
- 解 3 道第 0 種和 1 道第 1 種問題：1 + 1 + 1 + 2 = 5
- 解 1 道第 0 種和 2 道第 1 種問題：1 + 2 + 2 = 5
- 解 1 道第 2 種問題：5
範例 3：
輸入： target = 18, types = [[6,1],[3,2],[2,3]]
輸出： 1
解釋： 你只能藉由解出所有問題來得到 18 分。
解題思維：
其實本題就是變化版的背包問題（Knapsack Problem），參見這題。
一樣我們可以定義一個二維陣列 D，其中 D[i][j] 代表著在只考慮前 i 種問題得到 j 分的方法數。可以看到遞迴式為：
對於 j < 0，D[i][j] = 0；
對於 i == 0，D[0][0] = 1 、 D[0][j] = 0（j > 0）；
其餘情況，則是 D[i + 1][j] = max(D[i][j - c * marksi])，其中 0 ≦ c ≦ counti。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
