DA:dp

フィボナッチ数列

全探索

次のコードは，再帰関数を用いた全探索による解法です．ただし，fibonacci 関数の引数 n は正の整数であることを仮定しています．

def fibonacci(n):
    if n == 0 or n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))

しかしこれは無駄が多い実装です．fobonacci(n) を実行する際に，fibonacci(n-1) と fibonacci(n-2) が実行されますが，fibonacci(n-1) の中でも fibonacci(n-2) がまた実行されることになります．よって，このままでは全く同じ計算を何回も繰り返すことになります．

全探索（既に計算したものをメモしておく戦略）

これを，既に計算したものは結果を保存して使い回す，という戦略で計算してみましょう．ここでは，n=10ならば，長さ10のリストを準備して，その k 番目の要素に fibonacci(k+1) が格納されるようにします．この戦略を実装したものが，次のコードです．（ただし， n=1 の場合に，リスト memo の長さは 1 なので， "memo[1] = 1" のところでエラーが出てしまう．これを避けるため，memo の長さを n+1 としてあります．）

def fibonacci(n):
    if memo[n] != 0:
        return memo[n]
    a = fibonacci(n-1) + fibonacci(n-2)
    memo[n] = a
    return a

n = 10

memo = [0 for i in range(n+1)]
memo[0] = 1
memo[1] = 1

print(fibonacci(n))

動的計画法

フィボナッチ数列の場合，普通に小さい方から順に計算していくのが動的計画法になっていいます．長さ n のリスト memo を準備して，0 番目から順に埋めていけば良い，ということになります．（ただし， n=1 の場合に，リスト memo の長さは 1 なので， "memo[1] = 1" のところでエラーが出てしまう．これを避けるため，memo の長さを n+1 としました．）

def fibonacci_dp(n):
    memo = [0 for i in range(n+1)]
    memo[0] = 1
    memo[1] = 1
    for i in range(2,n+1):
        memo[i] = memo[i-1] + memo[i-2]
    return memo[n-1]

print(fibonacci_dp(10))

Frog 1

再帰関数で解く方法

def solve(n):
    if n == 0:
        return 0
    if n == 1:
        return h[2]

    a = #ここを埋めてください
    b = #ここを埋めてください

    return min(a, b)

N = 7
h = [2, 9, 4, 5, 1, 6, 10]
print(solve(N-1))

ナップサック問題

動的計画法による解法

N = 4
products = ((2,3), (1,2), (3,6), (2,1))
W = 8

memo = [[0 for i in range(W+1)] for i in range(N+1)]

for i in range(1, N+1):
    for j in range(1, W+1):
        w = products[i-1][0]
        v = products[i-1][1]
        if j - w < 0:
            a = 0
        else:
            a = memo[i-1][j-w] + v
        b = memo[i-1][j]
        memo[i][j] = max(a, b)

for i in range(len(memo)):
    print(memo[I])