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)
