動態規劃大全

fib/樓梯

1
2
3
4
5
6
7
8
9
10
11
12
13
def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b

def climb_stairs(n):
    a, b = 1, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b

股票買賣 只能交易一次

1
2
3
4
5
6
7
def max_profit_once(prices):
    min_price = 10**18
    max_profit = 0
    for p in prices:
        min_price = min(min_price, p)
        max_profit = max(max_profit, p - min_price)
    return max_profit

股票買賣 可以無限次交易

1
2
3
4
5
def max_profit_unlimited(prices):
    profit = 0
    for i in range(1, len(prices)):
        profit += max(0, prices[i] - prices[i-1])
    return profit

股票買賣 最多交易 k 次

1
2
3
4
5
6
7
8
9
10
11
12
def max_profit_k(prices, k):
    n = len(prices)
    if n == 0: return 0
    if k >= n//2:
        return max_profit_unlimited(prices)
    dp = [[0]*n for _ in range(k+1)]
    for i in range(1, k+1):
        best = -prices[0]
        for j in range(1, n):
            dp[i][j] = max(dp[i][j-1], prices[j]+best)
            best = max(best, dp[i-1][j]-prices[j])
    return dp[k][n-1]

LIS求長度

1
2
3
4
5
6
7
8
9
10
11
import bisect

def lis_binary(a):
    d = []
    for x in a:
        i = bisect.bisect_left(d, x)
        if i == len(d):
            d.append(x)
        else:
            d[i] = x
    return len(d)

LIS求序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import bisect

def LIS_path(a):
    n = len(a)
    L = []
    pos = [0]*n
    parent = [-1]*n

    for i, x in enumerate(a):
        j = bisect.bisect_left(L, x)
        if j == len(L):
            L.append(x)
        else:
            L[j] = x
        pos[i] = j
        if j > 0:
            # 找上一層的位置（O(n) 做法）
            for k in range(i-1, -1, -1):
                if pos[k] == j-1 and a[k] < x:
                    parent[i] = k
                    break

    # 回溯
    length = len(L)
    cur = -1
    for i in range(n-1, -1, -1):
        if pos[i] == length-1:
            cur = i
            break

    res = []
    while cur != -1:
        res.append(a[cur])
        cur = parent[cur]
    return res[::-1]

最大子段和

1
2
3
4
5
6
7
def max_subarray(a):
    cur = 0
    best = -10**18
    for x in a:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

0/1 背包

1
2
3
4
5
6
7
def knapsack_01(W, wt, val):
    n = len(wt)
    dp = [0]*(W+1)
    for i in range(n):
        for w in range(W, wt[i]-1, -1):
            dp[w] = max(dp[w], dp[w-wt[i]] + val[i])
    return dp[W]

完全背包

1
2
3
4
5
6
7
def complete_knapsack(W, wt, val):
    n = len(wt)
    dp = [0]*(W+1)
    for i in range(n):
        for w in range(wt[i], W+1):
            dp[w] = max(dp[w], dp[w-wt[i]] + val[i])
    return dp[W]

LCS求長度

1
2
3
4
5
6
7
8
9
10
11
def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if a[i] == b[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    return dp[n][m]

LCS求字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def lcs_seq(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n):
        for j in range(m):
            if a[i]==b[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j])
    i, j = n, m
    res=[]
    while i>0 and j>0:
        if a[i-1]==b[j-1]:
            res.append(a[i-1])
            i-=1; j-=1
        elif dp[i-1][j] >= dp[i][j-1]:
            i-=1
        else:
            j-=1
    return res[::-1]

最少硬幣

1
2
3
4
5
6
7
8
def coin_change_min(coins, target):
    INF = 10**18
    dp = [INF]*(target+1)
    dp[0]=0
    for c in coins:
        for t in range(c, target+1):
            dp[t] = min(dp[t], dp[t-c]+1)
    return dp[target] if dp[target] < INF else -1

硬幣組合

1
2
3
4
5
6
7
def coin_change_ways(coins, target):
    dp = [0]*(target+1)
    dp[0] = 1
    for c in coins:
        for t in range(c, target+1):
            dp[t] += dp[t-c]
    return dp[target]

110商競 硬幣(子集和問題)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
coins = list(map(int, input().split()))

max_sum = sum(coins)
dp = [False]*(max_sum+1)
dp[0] = True

for c in coins:
    for s in range(max_sum, c-1, -1):
        if dp[s-c]:
            dp[s] = True

res = [i for i in range(1, max_sum+1) if dp[i]]
print(len(res))
print(*res)