動的計画法
小銭の払い方
額面ごとの一次元DPで、指定額を作る順序を区別しない硬貨の組合せ数を求めます。
- TIME
- O(ad)
- SPACE
- O(a)
a = 金額、d = 額面数 / 上限: 金額0〜10,000、重複なしの額面100個以下
金額と重複しない硬貨の額面を指定します。
動的計画法
額面ごとの一次元DPで、指定額を作る順序を区別しない硬貨の組合せ数を求めます。
a = 金額、d = 額面数 / 上限: 金額0〜10,000、重複なしの額面100個以下
金額と重複しない硬貨の額面を指定します。