1、使用场景
一般与最优化相关的重构解（子集的最优解如何获取是关键）
贪心算法是动态规划的一种
- 最优子集
- 重复问题
2、思维，而非算法
"""
从斐波那怯数列
递归、非递归
"""
# 斐波那切数列：递归
def f(n):
if n==1 or n==2:
return 1
return f(n-1)+f(n-2)
# 斐波那切数列，非递归;
# 使用列表缓存数据
# 非递归即可落实动态规划
def f2(n):
f_list = [0,1] # n=0 无效
for i in range(2,n+1): # i取到n,获取f_list[n]
f_list.append(f_list[i-1]+f_list[i-2])
# print(f_list)
return f_list[n]
# print(f2(100))
3、动态规划
最优子（自己总结递推时）
重复子问题=>需要的子问题存储起来
"""
出售价格与钢条长度之间关系
[0,1,5,8,9,10,17,17,20,24,30] # 1-10
长度为n的不同切割方案，最佳是？
# 暴露解法：
2的n-1次方（有n-1的切割点，切和不切2种选择）
3.1 递归方法
n=1,1
n=2 :切一下1+1=2，不切5，最优5
n=3:不切r[3],切1刀 r[1]+r[2]=6,切2刀r[1]*3=3;最优8
n=4 r[4],r[2]+r[2],r[1]+r[3],r[1]*4, 最优10
"""
price = [0,1,5,8,9,10,17,17,20,24,30]
n=9 # n大于10会有异常
r=[0,1] # r[1]=1 最优解
if n>1:
for i in range(2,n+1):
res = price[i] # 一刀不切
for j in range(1,i//2+1): # 从0开始越界；截止到一半即可
res = max(r[j]+r[i-j],res) # 分割为i段和n-i段
# print(j)
r.append(res)
# print(r)
print(r[n])
# 优化，n长，即为一不切p[n],或者切一刀r[n-1]+p[1]
3.2 最优方案下如何切
记录左边切下的长度（左边不切割）
n=8,
n=9,3+6
n=10,10
当前我是对半处理，因为有重叠；
现在考虑左边i不切割，右边切割，最优方案是r[n-i]
最后n则是max(p[i]+r[n-i]) #i从1到n
from copy import deepcopy
def cut_soultion(p,n):
r=[0] # 最优解
s=[0] # 最优解下左边切割长度
for i in range(1,n+1): # i=1到n
res_r = 0 # 价格初始值
res_s=0 # 最优解下左边不切割部分
for j in range(1,i+1): # 1到i
# print(f"i={i},j={j}")
if p[j]+r[i-j]>res_r:
res_r=p[j]+r[i-j] # 更新
res_s =j
# print(res_s)
r.append(res_r) # 获取最优解
s.append(res_s)
print(s,r)
# s为切割值
cut_res=[]
# m=deepcopy(n) # 赋值是浅拷贝，避免n值改变
m=n
while m>0:
cut_res.append(s[m])
m -=s[m]
# print(cut_res)
return r[n],cut_res # r[n]即最优解，s为对应的切换值
price = [0,1,5,8,9,10,17,17,20,24,30]
print(cut_soultion(price,8))
4、实例+回溯
- 最重要的在于递归公式的获取
"""
最长公共子序列
一个序列的子序列是在该序列中删去若干元素后得到的
例如ABCD和BDF是ADCDEFG的子序列 (保持原顺序)
最长公共子序列LCS问题，给定两个序列X和Y,求X和Y最大的公共子序列
"""
x="ABBCBDE"
y="DBBCDB"
# LCS(x,y)="BBCD"
# 最长公共子序列
def LCS(x,y):
pass
# x的子序列，有2的n次方（n是x的长度）
# 有没有最优子结构，决定了是否可以使用动态规划
# 最后一位相等，则LCS(x[:n-1],y[:m-1])+1 长度
# 若最后一位不相等，则max(LCS(x[:n-1],y[:m]),LCS(x[:n],y[:m-1]))
# 若x[0]或y[0],则0 =>x或y的长度是0，则最长公共子序列的长度=0
def lcs_length(x, y):
m = len(x)
n = len(y)
c=[[0 for i in range(n+1)] for _ in range(m+1)] # _代表行，i代表列
# print(c)
# 初始化
for i in range(1,m+1): # x
for j in range(1,n+1): #y
if y[j-1]==x[i-1]: #?? i j位置上字符匹配时来自左上方+1
c[i][j]=c[i-1][j-1]+1
# print(i)
else: # 不相等
c[i][j] = max(c[i-1][j],c[i][j-1])
return c[m][n]
x="ABBCBDE"
y="DBBCDB"
# print(lcs_length(x,y))
# [[0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0],
# [0, 0, 1, 1, 1, 1, 1],
# [0, 0, 1, 2, 2, 2, 2],
# [0, 0, 1, 2, 3, 3, 3],
# [0, 0, 1, 2, 3, 3, 4],
# [0, 1, 1, 2, 3, 4, 4],
# [0, 1, 1, 2, 3, 4, 4]]
- 回溯，记录数据来源
def lcs_length(x, y):
m = len(x)
n = len(y)
c=[[0 for i in range(n+1)] for _ in range(m+1)] # _代表行，i代表列
b= [[0 for i in range(n+1)] for _ in range(m+1)] # 1左上方，2上方，3左方;用于回溯
# print(c)
# 初始化
for i in range(1,m+1): # x
for j in range(1,n+1): #y
if y[j-1]==x[i-1]: #?? i j位置上字符匹配时来自左上方+1
c[i][j]=c[i-1][j-1]+1
# print(i)
b[i][j]=1
else: # 不相等
# c[i][j] = max(c[i-1][j],c[i][j-1])
if c[i-1][j]>c[i][j-1]:
c[i][j]=c[i-1][j] # 来自上方
b[i][j]=2
else:
c[i][j]=c[i-1][j] # 来自左方
b[i][j]=3
return c[m][n],b
- 根据记录，来获取对应的字母
左上方是匹配，左方或上方则是不匹配
# 回溯
def lcs_trackback(x,y):
c,b=lcs_length(x,y)
i = len(x)
j = len(y)
res=[]
while i>0 and j>0:
if b[i][j]==1:#来自左上方=>匹配
res.append(x[i-1])
i-=1
j-=1
elif b[i][j]==2: # 来自上方，不匹配
i-=1
elif b[i][j]==3: # 来自左方，不匹配
j-=1
# print(res) # 获取的是反序
res.reverse()
return "".join(res)
x="ABBCBDE"
y="DBBCDB"
# print(lcs_length(x,y))
print(lcs_trackback(x,y))
5、参考：
动态规划
网友评论