---
# System prepended metadata

title: Problem 3-2
tags: [Recursion, week7, answer]

---

# Problem 3-2
###### tags: `week7` `Recursion` `answer`
難到哭
我覺得是對的（不確定），但至少我試了幾個自己假設的測資是對的
概念是放一個上去 剩下的比 上半＋那格的右邊 和 右半＋那格的上面 哪個剩比較少
有問題或bug再留言跟我說
![](https://i.imgur.com/pCHnbF1.jpg)

## Recusively
```python=1
[wa,ha] = map(int,input().split(' '))
[w1,h1] = map(int,input().split(' '))
[w2,h2] = map(int,input().split(' '))
[w3,h3] = map(int,input().split(' '))
def puzzle(w,h):
    global w1,h1,w2,h2,w3,h3
    if (w<w1 or h<h1) and ((w<w2 or h<h2)) and (w<w2 or h<h2):
        return w*h
    a =[]
    if w==w1 and h==h1 or w==w2 and h==h2 or w==w2 and h==h2:
        return 0
    if w>=w1 and h>=h1:
        a1 =[puzzle(w,h-h1)+puzzle(w-w1,h1),puzzle(w-w1,h)+puzzle(w1,h-h1)]
        a.append(min(a1))
    if w>=w2 and h>=h2:
        a2 =[puzzle(w,h-h2)+puzzle(w-w2,h2),puzzle(w-w2,h)+puzzle(w2,h-h2)]
        a.append(min(a2))
    if w>=w3 and h>=h3:
        a3 =[puzzle(w,h-h3)+puzzle(w-w3,h3),puzzle(w-w3,h)+puzzle(w3,h-h3)]
        a.append(min(a3))
    return min(a)
print((wa*ha)-puzzle(wa,ha))
```
## DP
```python=1
[wa,ha] = map(int,input().split(' '))
[w1,h1] = map(int,input().split(' '))
[w2,h2] = map(int,input().split(' '))
[w3,h3] = map(int,input().split(' '))
pset = dict()
def puzzle(w,h):
    global pset
    if (w,h) in pset:
        return pset[(w,h)]
    global w1,h1,w2,h2,w3,h3
    if (w<w1 or h<h1) and ((w<w2 or h<h2)) and (w<w2 or h<h2):
        return w*h
    a =[]
    if w==w1 and h==h1 or w==w2 and h==h2 or w==w2 and h==h2:
        return 0
    if w>=w1 and h>=h1:
        a1 =[puzzle(w,h-h1)+puzzle(w-w1,h1),puzzle(w-w1,h)+puzzle(w1,h-h1)]
        a.append(min(a1))
    if w>=w2 and h>=h2:
        a2 =[puzzle(w,h-h2)+puzzle(w-w2,h2),puzzle(w-w2,h)+puzzle(w2,h-h2)]
        a.append(min(a2))
    if w>=w3 and h>=h3:
        a3 =[puzzle(w,h-h3)+puzzle(w-w3,h3),puzzle(w-w3,h)+puzzle(w3,h-h3)]
        a.append(min(a3))
    pset.setdefault((w,h),min(a))
    return min(a)
print((wa*ha)-puzzle(wa,ha))
```
>[name=Pingju Hsieh]