###### tags: `ADA 5.3` `StampProblem 郵票問題`

# ADA 5.3: Stamp Problem

### 初步認識
#### 在不同數量面額的郵票內，湊出符合郵資的郵票，並且需要透過最少張數完成。

## Recursive 暴力解
#### 1+min(Sn-3, Sn-5, Sn-7, Sn-12) Sn為現有所需郵資

### 公式 For Recursive
#### v: 現有郵票(1張7元, 3張9元, 2張10元...)
#### n: 所需郵資
#### r_min:所需最小郵票數量
#### r: 各郵票張數

#### 透過暴力解時間複雜度為k的n次方

## OPT 最佳解
#### 郵資為S(i)最少需要S(n)郵票，現有k種郵資


#### Si = 1+Si-v1 (暫時視為1為某張郵票的郵資)

## 透過Bottom-up貼出郵票

### 公式 For OPT


#### 時間複雜度(kn)

---

## 解題疑問

#### 若都數偶數郵票如何解奇術郵資？有超過就好？