淺談動態規劃

Q：什麼是動態規劃呢？

A：有記憶的遞迴！

一般遞迴 Fibonacci

1
2
3
4
5
6
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(10))

fib(n-1) 和 fib(n-2) 會被重複計算很多次

動態規劃 Fibonacci

1
2
3
4
5
6
7
8
9
10
11
memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

print(fib(10))

將已計算過的結果存起來，可以大幅提高效率

硬幣 DP（找零的解法數）

1
2
3
4
5
6
7
8
9
10
coins = [1, 2, 5]
n = 5
dp = [0]*(n+1)
dp[0] = 1

for c in coins:
    for i in range(c, n+1):
        dp[i] += dp[i-c]

print(dp[n])

dp[i] 代表湊成 i 元的方法數

DP 填表過程

i dp[i] 初始值 dp[i-c] c 更新後 dp[i]
1 0 dp[0]=1 1 1
2 0 dp[1]=1 1 1
2 1 dp[0]=1 2 2
3 0 dp[2]=2 1 2
3 2 dp[1]=1 2 3
4 0 dp[3]=3 1 3
4 3 dp[2]=2 2 5
5 0 dp[4]=5 1 5
5 5 dp[3]=3 2 8
5 8 dp[0]=1 5 9

最終 dp = [1,1,2,3,5,9]
所以湊成 5 元的方法共有 9 種

image