1. 硬幣組合

如果我們有面值為1元、3元和5元的硬幣若干枚窿吩，如何用最少的硬幣湊夠11元？

參考資料

假設(shè)d[i]為湊滿i元所需最少的硬幣數(shù)倾哺，那么：

可以得出狀態(tài)轉(zhuǎn)移方程：dp[i] = min(d[i-value[j]) + 1昧穿，參考代碼：

import sys

# 需要用硬幣湊滿的錢數(shù)
amount = 12
# 硬幣的種類
coins = [1, 3, 5]

def coin_dynamic(amount, coins):
    dp = [0]
    for i in range(1, amount + 1):
        dp.append(sys.maxsize)
        for j in range(len(coins)):
            if coins[j] <= i and dp[i - coins[j]] + 1 < dp[i]:
                dp[i] = dp[i - coins[j]] + 1
    return dp

2. 0-1背包問題

假設(shè)我們有n件物品胶逢，分別編號為1, 2...n初坠。其中編號為i的物品價值為value[i]彭雾，它的重量為weight[i]半沽。為了簡化問題者填，假定價值和重量都是整數(shù)值♂Ｍ校現(xiàn)在重挑，假設(shè)我們有一個背包，它能夠承載的重量是capacity∶В現(xiàn)在史煎，我們希望往包里裝這些物品篇梭，使得包里裝的物品價值最大化恬偷，那么我們該如何來選擇裝的東西呢坦康？

參考資料

首先我們先構(gòu)建一個表格dp[i][j]滞欠，橫軸為背包的容納重量（從1到背包的實際最大容納），縱軸為各個可選擇的物品肆良。而表格中的每個單元格表示的是使用i與前的物品、且保證總重量不大于j情況下背包能容納物品的最大價值隧哮。

嘗試填充完畢后曲秉，我們可以得到一個結(jié)論：在i行j列的最大值可以說是（i-1行[即不取i物品]j列的值) 和 (i物品的價值 + i-1行j-i物品價值列的值[即取了i物品的價值])榆鼠，寫成狀態(tài)轉(zhuǎn)移方程即為：`dp[i][j] = max{dp[i-1][j], dp[i-1][j-value[i]] + value[i]}妆够，對應(yīng)的代碼如下：

# n個物體的重量(w[0]無用)
weight = [1, 4, 3, 1]
# n個物體的價值(p[0]無用)
value = [1500, 3000, 2000, 2000]
# 計算n的個數(shù)
n = len(weight) - 1
# 背包的載重量
capacity = 5
# 裝入背包的物體的索引
x = []

def bag_dynamic(weight, value, capacity, x):
    n = len(weight)
    weight.insert(0, 0)
    value.insert(0, 0)

    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if j >= weight[i]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
            else:
                dp[i][j] = dp[i - 1][j]
    j = capacity
    for i in range(n, 0, -1):
        if dp[i][j] > dp[i - 1][j]:
            x.append(i)
            j = j - weight[i]

    return dp[n][capacity]

3. CPU雙核問題

雙核CPU的兩個核能夠同時的處理任務(wù)家妆，現(xiàn)在有n個已知數(shù)據(jù)量的任務(wù)需要交給CPU處理，假設(shè)已知CPU的每個核1秒可以處理1kb伤极，每個核同時只能處理一項任務(wù)蛹找。n個任務(wù)可以按照任意順序放入CPU進行處理庸疾，現(xiàn)在需要設(shè)計一個方案讓CPU處理完這批任務(wù)所需的時間最少炊豪，求這個最小的時間牵舱。

要使CPU處理時間最少，就要充分利用其雙核芜壁，使其達到負載均衡。所以該問題的實質(zhì)就是將數(shù)組分成兩部分塞淹，使得兩部分的和的差最小窟蓝。

weight = [0, 3072, 3072, 7168, 3072, 1024]  # 假設(shè)進入處理的的任務(wù)大小
weight = list(map(lambda x: int(x / 1024), weight))  # 轉(zhuǎn)化下
value = weight  # 這題的價值和任務(wù)重量一致
capacity = int(sum(weight) / 2 + 1)  # 背包承重為總?cè)蝿?wù)的一半


def dynamic_cpu(weight, value, capacity):
    dp = [[0 for _ in range(capacity + 1)] for _ in range(len(weight))]

    for i in range(1, len(value)):
        for j in range(1, capacity + 1):
            if j >= value[i]:
                dp[i][j] = max(dp[i - 1][j], value[i] + dp[i - 1][j - weight[i]])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[-1][-1]


print(dynamic_cpu(weight, value, capacity))

4. LIS-最長非降子序列

一個序列有N個數(shù)：A[1],A[2],…,A[N]运挫，求出最長非降子序列的長度(子序列不必連續(xù)，但不能破壞原序列的順序匈挖，子串必須要連續(xù)）翘瓮。

參考文章

定義d[i]為A[i]位置上的最長非降子序列長度踊赠，所以：

 d[0] = 1  
 d[1] = d[0] + 1 (A[1] >= A[0])  
      = 1 (A[1] < A[0])
 d[2] = d[1] + 1 (A[2] >= A[1])
      = d[0] + 1 (A[0] <= A[2] <= A[1])
      = 1 (A[2] < A[0], A[2] < A[1])
 ......

所以可以得到狀態(tài)轉(zhuǎn)移方程：d[i] = max{1, d[j]+1}(其中j<i, A[j]<=A[i])筐带，代碼如下：

def lis(arr):
    num = len(arr)
    d = [0] * num
    max_len = 1
    for i in range(num):
        d[i] = 1
        for j in range(i):
            if arr[j] <= arr[i] and d[i] < d[j] + 1:
                d[i] = d[j] + 1
            if d[i] > max_len:
                max_len = d[i]
    return max_len


print(lis([2, 1, 5, 3, 6, 4, 8, 9, 7]))

此時的時間復(fù)雜度為O(N^2)缤灵，還有一種巧妙的方法可以將復(fù)雜度降為O(n * logN)。

定義suq為最長遞增子序列腮出，它是一個有序數(shù)組胚嘲。

step 1，將arr[0]有序放入suq娶吞，則suq=[2];

step 2材部，將arr[1]有序放入乐导，因為arr[1]<suq[-1]（小于有序數(shù)組最后一個數(shù)）晋涣，所以將suq[-1]替換為arr[1]蔼夜，suq=[1];

step 3求冷，將arr[2]有序放入，此時arr[2]>suq[-1]（大于有序數(shù)組最后一個數(shù)）窍霞，所以將suq尾部添加arr[2]匠题，suq=[1,5];

step 4，將arr[3]有序放入但金，此時如step 2情況梧躺，suq=[1,3];

step 5，同step 3傲绣，suq=[1,3,6];

step 6，同step 2巩踏，suq=[1,3,4];

step 7秃诵，同step 3，suq=[1,3,4,8];

step 8塞琼，同step 3菠净，suq=[1,3,4,8,9];

step 9，同step 2彪杉，將arr[8]替換suq[3]毅往，suq=[1,3,4,7,9]

所以最長遞增子序列長度為len(suq)=5。

上述的插入分兩種情況派近，第一種：arr[i]>=suq[-1]攀唯，尾插；第二種：arr[i]<suq[-1]渴丸，將arr[i]替換掉suq中比其大的第一個元素(此時可以用二分法查找）侯嘀，每一個插入復(fù)雜度為O(logN)，總復(fù)雜度為O(N * logN)谱轨。

def binary_search(suq, l, h, key):
    if suq[h] <= key:
        return h+1
    while l < h:
        mid = (l+h) // 2
        if suq[mid] <= key:
            l = mid + 1
        else:
            h = mid
    return l

def lis_bs(arr):
    num = len(arr)
    suq = arr[0:1]
    max_len = 1
    for i in range(1, num):
        point = binary_search(suq, 0, max_len-1, arr[i])
        if point <= max_len - 1:
            suq[point] = arr[i]
        else:
            suq.insert(point, arr[i])
            max_len += 1
    return max_len

print(lis_bs([2, 1, 5, 3, 6, 4, 8, 9, 7]))

5. LCS-最長公共子序列

給定序s1=[1,3,4,5,6,7,7,8],s2=[3,5,7,4,8,6,7,8,2]戒幔，s1和s2的相同子序列，且該子序列的長度最長土童，即是LCS诗茎。

參考文章

可以得出以下結(jié)論：

如果s1和s2的最后一個元素相等，那么s1和s2的LCS就等于除去最后一個元素的s1和除去最后一個元素的s2的LCS再加上它們相等的最后一個元素献汗；

如果s1和s2最后一個元素不想等敢订，那么其LCS就等于(除去最后一個元素的s1和s2的LCS)和(除去最后一個元素的s2和s1的LCS)中更大的一個王污。

代碼如下：

s1 = [1, 3, 4, 5, 6, 7, 7, 8]
s2 = [3, 5, 7, 4, 8, 6, 7, 8, 2]


def lcs(s1, s2):
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]


print("max LCS number:", lcs(s1, s2))

6. 組成SUM的方案數(shù)

給定一個有n個正整數(shù)的數(shù)組A和一個整數(shù)sum,求選擇數(shù)組A中部分數(shù)字和為sum的方案數(shù)。
當(dāng)兩種選取方案有一個數(shù)字的下標不一樣,我們就認為是不同的組成方案枢析。

同樣玉掸，我們用dp[i][j]表示用前i個數(shù)字湊到j(luò)最多有多少種方案，那么可得：

# 當(dāng)不用i個數(shù)字時能湊到j(luò)的最多情況
dp[i][j] = dp[i-1][j]
# 用了i時醒叁，只需看原來湊到j(luò)-arr[i]的最多情況
dp[i][j] += dp[i-1][j-arr[i]]

代碼如下：

def sum_combination(arr, sum):
    length = len(arr)

    dp = [[1] + [0] * sum for _ in range(length + 1)]

    for i in range(1, length + 1):
        for j in range(1, sum + 1):
            if j - arr[i - 1] >= 0:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i - 1]]
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[length][sum]


print(sum_combination([5, 5, 10, 2, 3], 10))

7. 連續(xù)子數(shù)組的最大和

上一章數(shù)組篇談到過這個問題司浪，下面我們看一下如何能用一種更簡便更易理解的方式來解決吧。

定義dp[i]表示以第i個元素為結(jié)尾的連續(xù)子數(shù)組的最大和把沼，則有狀態(tài)方程 dp[i]=max{dp[i-1]+a[i], a[i]}啊易。

代碼如下：

def max_subarray(arr):
    dp = [arr[0]] + [0] * (len(arr)-1)

    for i in range(1, len(arr)):
        dp[i] = max(dp[i-1]+arr[i], arr[i])

    return max(dp)

print(max_subarray([-1,2, 1]))

8. 暗黑數(shù)

這道題超酷的!

一個只包含’A’、’B’和’C’的字符串饮睬，如果存在某一段長度為3的連續(xù)子串中恰好’A’租谈、’B’和’C’各有一個，那么這個字符串就是純凈的捆愁，否則這個字符串就是暗黑的割去。例如：

BAACAACCBAAA 連續(xù)子串”CBA”中包含了’A’,’B’,’C’各一個，所以是純凈的字符串

AABBCCAABB 不存在一個長度為3的連續(xù)子串包含’A’,’B’,’C’,所以是暗黑的字符串

你的任務(wù)就是計算出長度為n的字符串(只包含’A’昼丑、’B’和’C’)呻逆，有多少個是暗黑的字符串。

從第一位開始不斷往后推算暗黑數(shù)的排列總數(shù)菩帝，定義f(n)為n位上暗黑數(shù)的排列總數(shù)咖城，假設(shè)S(n)為n與n-1相同的排列數(shù)，D(n)為n與n-1不同的排列數(shù)呼奢。

那么宜雀，可以得到f(n-1) = S(n-1) + D(n-1) （1）。

如果n-1與n-2相同握础，那么新增字母ABC都可以辐董，有3*S(n-1)種可能；如果n-1與n-2不同弓候，那么新增字母只能是n-1與n-2中的一個郎哭，有2*D(n-1)種可能；

由此可得：f(n) = 3\*S(n-1) + 2\*D(n-1) = 2\*f(n-1) + S(n-1) (2)

我們繼續(xù)分析菇存，如果n-1與n-2相同夸研，那么之后有S(n-1)種可能是n與n-1相同的，有2*S(n-1)種可能是n與n-1不同的依鸥；如果n-1與n-2不同亥至，有D(n-1)種可能是n與n-1相同的，D(n-1)種可能是n與n-1不同的。

由此又可得 S(n) = S(n-1) + D(n-1)姐扮，結(jié)合上述式(1) f(n-1) = S(n-1) + D(n-1)可得： S(n) = f(n-1)絮供。

代入式(2)可得：f(n) = 2*f(n-1) + f(n-2)。

代碼水到渠成：

# 遞推
def dark_num(arr):
    dp = []
    dp[0], dp[1] = 3, 9
    if len(arr) < 3:
        return dp[len(arr)-1]
    dp += [0] * (len(arr) - 2)
    for i in range(2, len(arr)):
        dp[i] = 2 * dp[i-1] + dp[i-2]
    return dp[len(arr)-1]
    
 # 遞歸
 def dark_num(arr):
    if arr == 1:
        return 3
    elif arr==2:
        return 9
    else:
        return 2*dark_num(arr-1) + dark_num(arr-2)