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 s in range(1, W+1):
        w = products[i-1][0] #i番目の品物の重さ
        v = products[i-1][1] #i番目の品物の価値

        ########## ここから ##########
        # a = i番目の品物を選ぶ場合の価値の総和（s）
        # b = i番目の品物を選ばなかった場合の価値の総和
        ########## ここまで ##########

        memo[i][s] = max(a, b)

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