[Python] 算法心得—动态规划

1. 硬币组合

如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

参考资料

假设d[i]为凑满i元所需最少的硬币数，那么：

d[i]	解释
d[0] = 0	0
d[1] = 1	需要从面值不大于1元的硬币中选择，结果为1
d[2] = d[2-1] + 1 = 2	从面值不大于2元的硬币中选择，符合要求的硬币面值为：1元
d[3] = d[3-3] + 1 = 1	符合要求的硬币面值为：1元/3元，含有3元的硬币d[3]=d[3-3]+1=1，不含3元的硬币d[3]=d[3-1]+1=d[2]+1 =3
...	...

可以得出状态转移方程：dp[i] = min(d[i-value[j]) + 1，参考代码：

import sys

# 需要用硬币凑满的钱数
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背包问题

假设我们有n件物品，分别编号为1, 2...n。其中编号为i的物品价值为value[i]，它的重量为weight[i]。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是capacity。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？

参考资料

首先我们先构建一个表格dp[i][j]，横轴为背包的容纳重量（从1到背包的实际最大容纳），纵轴为各个可选择的物品。而表格中的每个单元格表示的是使用i与前的物品、且保证总重量不大于j情况下背包能容纳物品的最大价值。

尝试填充完毕后，我们可以得到一个结论：在i行j列的最大值可以说是（i-1行[即不取i物品]j列的值) 和 (i物品的价值 + i-1行j-i物品价值列的值[即取了i物品的价值])，写成状态转移方程即为：`dp[i][j] = max{dp[i-1][j], dp[i-1][j-value[i]] + value[i]}，对应的代码如下：

# n个物体的重量(w[0]无用)
weight = [1, 4, 3, 1]
# n个物体的价值(p[0]无用)
value = [1500, 3000, 2000, 2000]
# 计算n的个数
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的两个核能够同时的处理任务，现在有n个已知数据量的任务需要交给CPU处理，假设已知CPU的每个核1秒可以处理1kb，每个核同时只能处理一项任务。n个任务可以按照任意顺序放入CPU进行处理，现在需要设计一个方案让CPU处理完这批任务所需的时间最少，求这个最小的时间。

要使CPU处理时间最少，就要充分利用其双核，使其达到负载均衡。所以该问题的实质就是将数组分成两部分，使得两部分的和的差最小。

weight = [0, 3072, 3072, 7168, 3072, 1024]  # 假设进入处理的的任务大小
weight = list(map(lambda x: int(x / 1024), weight))  # 转化下
value = weight  # 这题的价值和任务重量一致
capacity = int(sum(weight) / 2 + 1)  # 背包承重为总任务的一半


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个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度(子序列不必连续，但不能破坏原序列的顺序，子串必须要连续）。

参考文章

定义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])
 ......

所以可以得到状态转移方程：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]))

此时的时间复杂度为O(N^2)，还有一种巧妙的方法可以将复杂度降为O(n * logN)。

定义suq为最长递增子序列，它是一个有序数组。

step 1，将arr[0]有序放入suq，则suq=[2];

step 2，将arr[1]有序放入，因为arr[1]<suq[-1]（小于有序数组最后一个数），所以将suq[-1]替换为arr[1]，suq=[1];

step 3，将arr[2]有序放入，此时arr[2]>suq[-1]（大于有序数组最后一个数），所以将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中比其大的第一个元素(此时可以用二分法查找），每一个插入复杂度为O(logN)，总复杂度为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。

参考文章

可以得出以下结论：

如果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的方案数

给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。
当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。

同样，我们用dp[i][j]表示用前i个数字凑到j最多有多少种方案，那么可得：

# 当不用i个数字时能凑到j的最多情况
dp[i][j] = dp[i-1][j]
# 用了i时，只需看原来凑到j-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. 连续子数组的最大和

上一章数组篇谈到过这个问题，下面我们看一下如何能用一种更简便更易理解的方式来解决吧。

定义dp[i]表示以第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. 暗黑数

这道题超酷的!

一个只包含’A’、’B’和’C’的字符串，如果存在某一段长度为3的连续子串中恰好’A’、’B’和’C’各有一个，那么这个字符串就是纯净的，否则这个字符串就是暗黑的。例如：

BAACAACCBAAA 连续子串”CBA”中包含了’A’,’B’,’C’各一个，所以是纯净的字符串

AABBCCAABB 不存在一个长度为3的连续子串包含’A’,’B’,’C’,所以是暗黑的字符串

你的任务就是计算出长度为n的字符串(只包含’A’、’B’和’C’)，有多少个是暗黑的字符串。

从第一位开始不断往后推算暗黑数的排列总数，定义f(n)为n位上暗黑数的排列总数，假设S(n)为n与n-1相同的排列数，D(n)为n与n-1不同的排列数。

那么，可以得到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)

我们继续分析，如果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)，结合上述式(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)