## 2019年1月5日土曜日

### Algorithm - Python - メモリは役に立つ(硬貨列問題、辞書の作成と検索、例外、再帰探索でのメモ化)

コード

Python 3

```#!/usr/bin/env python3
def coins(row: list, table: dict) -> (int, dict):
'''
>>> coins([14, 3, 27, 4, 5, 15, 1], {})
(61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
'''
if len(row) == 0:
table[0] = (0, 1)
return 0, table
if len(row) == 1:
table[1] = (row[0], 2)
return row[0], table
skip = coins(row[1:], table)[0]
pick_skip = coins(row[2:], table)[0] + row[0]
pick_pick = coins(row[4:], table)[0] + row[0] + row[1]
if skip >= pick_skip and skip >= pick_pick:
result = skip
table[len(row)] = (result, 1)
elif pick_skip >= skip and pick_skip >= pick_pick:
result = pick_skip
table[len(row)] = (result, 2)
else:
result = pick_pick
table[len(row)] = (result, 3)
return result, table

def coins_memo(row: list, memo: dict) -> (int, dict):
'''
>>> coins([14, 3, 27, 4, 5, 15, 1], {})
(61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
'''
if len(row) == 0:
memo[0] = (0, 1)
return 0, memo
if len(row) == 1:
memo[1] = (row[0], 1)
return row[0], memo
if len(row) in memo:
return memo[len(row)][0], memo
skip = coins_memo(row[1:], memo)[0]
pick_skip = coins_memo(row[2:], memo)[0] + row[0]
pick_pick = coins_memo(row[4:], memo)[0] + row[0] + row[1]
if skip >= pick_skip and skip >= pick_pick:
result = skip
memo[len(row)] = (result, 1)
elif pick_skip >= skip and pick_skip >= pick_pick:
result = pick_pick
memo[len(row)] = (result, 2)
else:
result = pick_pick
memo[len(row)] = (result, 3)
return result, memo

if __name__ == '__main__':
import doctest
doctest.testmod()
```

```\$ ./sample2.py -v
Trying:
coins([14, 3, 27, 4, 5, 15, 1], {})
Expecting:
(61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
ok
Trying:
coins([14, 3, 27, 4, 5, 15, 1], {})
Expecting:
(61, {1: (1, 2), 0: (0, 1), 2: (16, 3), 3: (20, 3), 4: (20, 1), 5: (47, 2), 6: (47, 1), 7: (61, 2)})
ok
__main__
2 items passed all tests:
1 tests in __main__.coins
1 tests in __main__.coins_memo
2 tests in 3 items.
2 passed and 0 failed.
Test passed.
\$
```