动态规划学习(Python)
阅读本文大概需要 19 分钟。
前言
动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),状态转移函数是指从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)。
重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要 o(1) 时间复杂度,准确的说,动态规划是利用空间去换取时间的算法.
判断是否可以利用动态规划求解,第一个是判断是否存在重叠子问题。
为了学习动态规划算法，结合相关案例进行学习分析。
实战分析
案例一
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
分析：
假定 n=3，考虑最后一步的情况，要么从第二级台阶走一步上来，或者从第一级台阶走两步上来。如果说从地面走到第二级台阶有 X 种走法，从地面走到第一级台阶有 Y 种走法，那么从地面走到第十级台阶一共有 X+Y 种走法。即 F(3) = F(2)+F(1)。
可以看出，该案例的分析存在重叠子问题，所以可以使用动态规划。最终得到动态规划的三要素：
边界：F(1)=1，F(2)=2
最优子结构：F(3)的最优子结构即 F(1) 和 F(2)
状态转移函数：F(n) = F(n-1)+F(n-2)
代码实现：
import timeit
def climb1(n):
'''
常规操作，采用递归的形式求解
:param n: n级台阶
:return: 走到终点有多少种方法
'''
if n <= 2:
return n
return climb1(n-1)+climb1(n-2)
def climb2(n):
'''
动态规划方法求解，代码较长，但是时耗短
:param n:n级台阶
:return:走到终点有多少种方法
'''
if n <= 2:
return n
a = 1 # 边界
b = 2 # 边界
temp = 0
for i in range(3, n + 1):
temp = a + b # 状态转移
a = b # 最优子结构
b = temp # 最优子结构
return temp
if __name__ == '__main__':
print(climb1(12))
print(climb2(12))
tt1 = timeit.repeat("climb1(12)", setup="from __main__ import climb1", number=1000)
print(min(tt1))
tt2 = timeit.repeat("climb2(12)", setup="from __main__ import climb2", number=1000)
print(min(tt2))
输出结果为：
233
233
0.02911975
0.0006569639999999821
案例二
给你一个整数list L, 如 L=[2,-3,3,50], 求L的一个连续子序列，使其和最大，输出最大子序列的和。
例如，对于L=[2,-3,3,50]， 输出53（分析：很明显，该列表最大连续子序列为[3,50]).
分析：
假设序列的起始位置为 m，终止位置为 n，其中 m<n。当 m=0，n=3 时，F(0,3) 表示L[0:3] 序列中最大子序列的和，需要根据之前的序列和进行比较，其中包括 L[0:1]，L[0:2]，L[1:2]，L[1:3]，L[2:3]。F(0,3) = max(sum(L[0:1]),sum(L[0:2]),sum(L[1:2]),sum(L[1:3]),sum(L[2:3]),sum(L[0:3]))，同理，F(0,2)=max(sum(L[0:1]), sum(L[0:2]), sum(L[1:2]))，其中 F(0,1) 即为 L[0]，所以 F(0,2) = max(L[1],F(0,1)+L[1])，所以该案例可以使用动态规划进行解析。
根据以上分析，可以得到动态规划的三要素：
边界：F(0,1) = L[0]
最优子结构：F(0,2) = max(L[1],F(0,1)+L[1])
状态转移方程：F(m,n) = max(L[n-1],F(m,n-1)+L[n-1])
将上述状态转移方程改成代码所能识别的形式，如下：
dp[i] = max(L[i], L[i] + dp[i - 1])
其中，i 代表数组中的第 i 个元素的位置；dp[i] 代表从 0 到 i 闭区间内，所有包含第 i 个元素的连续子数组中，总和最大的值。
在本案例中即为：
L = [2,-3,3,50]
dp = [2,-1,3,53]
代码实现：
import timeit
L = [4, -3, 3, 50]
# L=[-1,-1,-1,-1,-1,0]
def split_list1():
'''
动态规划求解， 代码较长，但是时耗短
:return:
'''
global L
Max,temp = L[0],0
for i in L:
temp = max(i,temp+i)
Max = max(Max,temp)
return Max
def split_list3():
'''
常规操作求解，代码简洁，时耗一般
:return:
'''
global L
Lx = [sum(L[i:j]) for i in range(len(L)) for j in range(i + 1, len(L) + 1)]
return max(Lx)
if __name__ == '__main__':
print(split_list1())
print(split_list3())
tt1 = timeit.repeat("split_list1()", setup="from __main__ import split_list1", number=1000)
print(min(tt1))
tt3 = timeit.repeat("split_list3()", setup="from __main__ import split_list3", number=1000)
print(min(tt3))
输出结果为：
54
54
0.001378185000000004
0.0038338319999999815
案例三
给你一个整数list L, 如 L=[-2,1,-3,4,-1,2,1,-5,4], 求L的一个非连续子序列，使其和最大，输出最大子序列的和。
这里非连续子序列的定义是，子序列中任意相邻的两个数在原序列里都不相邻。
例如，对于L=[-2,1,-3,4,-1,2,1,-5,4]， 输出11（分析：很明显，该列表最大非连续子序列为[1,4,2,4]).
分析：
利用动态规划的思路解题: 首先寻找最优子问题,[-2,1,-3,4,-1,2,1,-5,4],第一个最优子问题为 1（因为 -2<0，所以跳过 -2）,那么到下一个 4 时,其最优为当前值或者当前值加上上一个最优值,因而可以得到其递推公式。
状态转移方程：L[i] = max(max(L[0:i-1],0))+L[i] i>=2
L=[-2,1,-3,4,-1,2,1,-5,4] 根据上述方程计算后为 L=[-2,1,-3,5,0,7,6,2,11]
代码实现：
L=[-2,1,-3,4,-1,2,1,-5,4]
def split_list_other3():
global L
for i in range(2, len(L)):
L[i] = max(max(L[0:i - 1]), 0) + L[i]
return max(L)
案例四
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
分析：
由题可知，当 N=4 时，丑数为 F(2)2；因此动态规划的三要素即为：边界：F(1)=1最优子结构：F(4)=min(F(2)2,F(3)2,F(1)5)状态转移函数：F(N)=min(F[t1]2,F[t2]3,F[t3]*5)。其中 t1,t2,t3<N-1
关于 t1,t2,t3 的取值，依据 F(t1)*2 >F(N-1) F(t2)*3 >F(N-1) F(t3)*5 >F(N-1) 。
代码实现：
def getUglyNumber():
global n
if n<=2:
return n
S = [1]
t1,t2,t3 = 0,0,0
for i in range(1,n):
for j in range(i):
if S[j]*2 > S[i-1]:
t1 = j
break
for j in range(i):
if S[j]*3 > S[i-1]:
t2 = j
break
for j in range(i):
if S[j]*5 > S[i-1]:
t3 = j
break
S.append(min(S[t1]*2,S[t2]*3,S[t3]*5))
print(S)
return S[-1]
案例五
买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
分析：当数组为 prices= [7,1,5,3,6,4] 时，将 F(6) 记为第六天卖出股票赚取的利润，则想要 F(6) 为最大利润时，需要比较 F(5)获取的利润和 4-买入股票时的最小值，即为 F(6) = max(F(5),prices[5]-最小值。某天卖出的利润需要根据之前日期卖出的利润进行比较，所以可以采用动态规划进行解决。其中边界：F(1) = 0，最优子结构：F(6) 的最优子结构为 F(5)。
代码实现：
L = [7, 1, 5, 3, 6, 4]
# L = [1, 7, 5, 3, 6, 4]
def buy_shares1():
'''
常规方法
:return:
'''
global L
if len(L)<=1:
return 0
dp = [0]
for i in range(1,len(L)):
t = L[i] - min(L[0:i])
if t<0:
dp.append(L[i])
else:
dp.append(t)
return max(dp)
def buy_shares2():
'''
动态规划求解，根据状态转移方程进行计算。
:return:
'''
global L
if len(L)<=1:
return 0
dp = [0]
min_price = L[0]
for i in range(1,len(L)):
dp.append(max(dp[i-1],L[i]-min_price))
if min_price>L[i]:
min_price = L[i]
return dp[-1]
案例六
使用最小花费爬楼梯
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]
分析：当 cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 时，初始阶梯为 cost[0]，如果要到楼顶，只有两种方式，从第九层走一步，或者从第八层走两步。总结为动态规划的三因素：
边界：F(0) = 1,F(1)=100
最优子结构：F(10) 有最优子结构为 F(9) 和 F(8)
状态转移方程：F(10) = min(F(9)+cost[9],F(8)+cost[8])
代码实现：
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
def climb1():
global cost
cost.append(0)#楼顶不在cost的范围内,因此追加0作为楼顶标识
dp = cost[0:2]
for i in range(2,len(cost)):
dp.append(min(dp[i-2]+cost[i],dp[i-1]+cost[i]))
return dp[-1]
案例七
三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
分析：
以第四行为例，计算到达第四行每个点上的路径，F(4)=F(6)+L3，F(1)=min(F(6),F(5))+L3，F(8)=min(F(5),F(7))+L3，F(4)=F(7)+L3，最后对这四个结果取最小值。总结得到每一行两侧的数据，只有一条路径可以抵达，中间位置的点都有两条路径可以抵达，因此需要选择上一步的最小值。
动态规划的三要素：
边界：dp[0][0]=2
最优子结构：最后一行最小值为：min(4+dp[2][0],1+min(dp[2][0],dp[2][1]),8+min(dp[2][1],dp[2][2]),3+dp[2][2])
状态转移方程：如果i==0 or i==len(triangle[row]) 那么其转移方程为dp[i]=dp[0]triangle[row][i] dp[i]=dp[i-1]+triangle[row][i]
dp[i]=min(dp[i-1],dp[i])+triangle[row][i]
代码实现：
L = [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
def cal_walk_steps():
global L
min_steps = []
line_num = 1
if len(L) == 1:
return L[0][0]
dp = [[L[0][0]]]
for i in range(1,len(L)):
for j in range(len(L[i])):
dp.append([])
if j == 0:
dp[i].append(L[i][j]+dp[i-1][j])
elif j == len(L[i])-1:
dp[i].append(L[i][j]+dp[i-1][j-1])
else:
dp[i].append(min(dp[i-1][j-1],dp[i-1][j])+L[i][j])
return min(dp[len(L)-1])
案例八
硬币最少数量（凑齐n元最少需要几枚硬币）
假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 11 元，问如何组合才能使硬币的数量最少？
分析：当 money = 11 时，最优解为 F(6)+1,F(8)+1,F(10)+1，其中 F(6)为 money=6时的最优解，所以只要将 money 减少至 0，需要的次数即为硬币数。转化为公式即为 money = min(money-1,abs(money-3),abs(money-5))，考虑到负值的存在，加上绝对值判定。
代码实现：
money = 11
def get_coin_num():
global money
counts = 0
while money:
money = min(money-1,abs(money-3),abs(money-5))
counts += 1
return counts
案例九
砝码问题
有一组砝码，重量互不相等，分别为m1、m2、m3……mn；它们可取的最大数量分别为x1、x2、x3……xn。
现要用这些砝码去称物体的重量,问能称出多少种不同的重量。
现在给你两个正整数列表w和n， 列表w中的第i个元素w[i]表示第i个砝码的重量，列表n的第
i个元素n[i]表示砝码i的最大数量。i从0开始，请你输出不同重量的种数。
如：w=[1,2], n=[2,1], 则输出5（分析：共有五种重量：0,1,2,3,4）
分析：
重量组合由 w 列表和 n 列表形成的，dp = [[0,1,2],[0,2]] 表示 w 和 n 的不同组合结果，F([1],[2]) = dp[0]，F(w,n) = set(i+j for i in dp[0] for j in dp[1])，因此可知后一个结果都与上一个结果有关。
代码实现：
w = [1,2,3,4,5]
n = [2,1,1,1,1]
S = set([])
S.add(0)
for i in range(len(w)):
temp_S = S.copy()
for s in temp_S:
j = 1
while j <= n[i]:
S.add(s+j*w[i])
j += 1
print(S)
print(len(S))
案例十
最长回文子串
在一个英文字符串 L 中, 怎么找出最长的回文子串.
例如 L = "caayyhheehhbbbhhjhhyyaac", 那么它最长的回文子串是 "hhbbbhh".
分析：回文字符串的子串也是回文，比如 P[i,j]（表示以 i 开始以 j 结束的子串）是回文字符串，那么 P[i+1,j-1]也是回文字符串。这样最长回文子串就能分解成一系列子问题了。
首先定义状态方程和转移方程：
P[i,j]=0 表示子串[i,j]不是回文串。P[i,j]=1 表示子串[i,j]是回文串。
其中 P[i,i]=1，P[i,j] = 1 if P[i+1,j-1] == 1 and L[i]==L[j] else 0
代码实现：
L = 'caayyhheehhbbbhhjhhyyaac'
def manacher():
global L
maxlen = 0
start = 0
dp = [[0 for i in range(len(L))] for j in range(len(L))]
for i in range(len(L)):
dp[i][i] = 1
if i+1 < len(L) and L[i]== L[i+1]:
dp[i][i+1] = 1
maxlen = 2
start = i
for i in range(3,len(L)+1):
for j in range(len(L)-i+1):
k = i+j-1
if dp[j+1][k-1] == 1 and L[j] == L[k]:
dp[j][k] = 1
if i >maxlen:
start = j
maxlen = i
if maxlen >= 2:
return L[start:start+maxlen]
return None