一、斐波那契数列

Fn =Fn-1 + Fn-2

#子问题的重新计算
def fabnacci(n):if n == 1 or n == 2:return 1else:return fabnacci(n-1)+fabnacci(n-2)#非递归算法：动态规划思想DP
def fabnacci_no_rec(n):f = [0,1,1]if n >= 2:for i in range(n-2):num = f[-1]+f[-2]f.append(num)return f[n]

动态规划：最优子结构→递归式

二、钢条切割问题

1、自顶向下递归实现

某公司出售钢条，出售价格与钢条长度之间的关系如下表：

现有一段长度为n的钢条和上面的价格表，求切割钢条方案，使总收益最大

长度为n的钢条 有 2^(n-1)种切割方案

（1）递推式：

设长度为n的钢条最优收益为r_n，递推式为

r_n = max(p_n, r_1+r_n-1, r_2+r_n-2, r_3+r_n-3……, r_n-1+r_1)

p_n表示不切割

其他n-1个参数分别表示另外n-1种不同切割方案，对方案 i=1,2…,n-1：

        将钢条分为长度为 i 和n-i两段

        方案 i 的收益为切割两段的最有收益之和

考察所有的 i ，选择其中收益最大的方案

（2）简化递推式：

从钢条的左边切割下长度为 i 的一段，只对右边剩下的一段继续进行切割，左边的不再切割

递推式简化为：r_n = max(p_i + r_n-1)  1 <= i <= n-i

print(cut_rad_rec_1(p,9))

不做切割的方案可以描述为：左边一段长度为n，收益为p_n，剩余一段长度为0，收益为r_0=0

最优子结构：

可以将求解规模为n的原问题，划分为规模更小的子问题：完成一次切割后，可以将产生的两段钢条看成两个独立的钢条切割问题。

组合两个子问题的最优解，并在所有可能的两段切割方案中选取组合收益最大的，构成原问题的最优解。

钢条切割问题满足最优子结构：问题的最优解由相关子问题的最优解组合而成，这些子问题可以独立求解。

方法一：简化前写法

p = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]def cut_rod_rec_1(p, n):if n== 0:return 0else:res = p[n]for i in range(1,n):res = max(res, cut_rod_rec_1(p,i) + cut_rod_rec_1(p,n-i))return resprint(cut_rod_rec_1(p,9))

方法二：简化后写法

def cut_rod_rec_2(p, n):if n == 0:return 0else:res = 0for i in range(1,n+1):res = max(res, p[i] + cut_rod_rec_2(p,n-i))return res

速度更快

自顶向下递归实现效率差：时间复杂度 O(2^n)

2、动态规划解法——自底向上实现

递归算法由于重复求解相同子问题，效率极低

动态规划的思想：

        每个子问题只求解一次，保存求解结果

        之后需要此问题时，只需查找保存的结果

先算r_1, 存起来，再算r_2……

def cut_rod_dp(p, n):r = [0]for i in range(1, n+1):res = 0for j in range(1, i+1):res = max(res, p[j] + r[i-j])r.append(res)return r[n]

时间复杂度 O(n^2)

3、重构解

如何输出最优切割方案？

——对于每个子问题，保存切割一次时左边切下的长度

def cut_rod_extend(p, n):r = [0]s = [0]for i in range(1, n+1):res_r = 0  #记录价格最大值res_s = 0  #记录最优切割处for j in range(1, i+1):if p[j] + r[i-j] > res_r:res_r = p[j] + r[i-j]res_s = jr.append(res_r)s.append(res_s)return r[n], sdef cut_rod_solution(p, n):r, s = cut_rod_extend(p, n)ans = [] #存放最终切割方案while n > 0:ans.append(s[n])n -= s[n]return r, ans

什么问题可以使用动态规划？

1、量化子结构

        原问题的最优解中涉及多少个子问题

        在确定最优解使用哪些子问题时，需要考虑多少种选择

2、重叠子问题

三、最长公共子序列(LCS)

一个序列的子序列是在该序列中删去若干元素后得到的序列

最长公共子序列(LCS)问题：给定两个序列X和Y，求X和Y长度最大的公共子序列。

        例如：X=“ABBCBDE”   Y="DBBCDB"  LCS(X,Y)="BBCD"

应用场景：字符串相似度比对

暴力穷举时间复杂度： 2^(m+n) ， m、n为两个序列的长度

LCS是否具有动态规划的最优子结构性质？

 

 最后结果就是 c[m, n]

def lcs(x,y):m = len(x)n = len(y)c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]  #m+1 * n+1  初始化都是0b = [[0 for _ in range(n + 1)] for _ in range(m + 1)]  #记录方向箭头 1左上方 2上方 3左方for i in range(1, m+1):for j in range(1, n+1):if x[i-1] == y[j-1]:  #i j上的字符相等 匹配c[i][j] = c[i-1][j-1] + 1b[i][j] = 1elif c[i-1][j] > c[i][j-1]:  #i j上的字符不相等 不匹配 从上方来c[i][j] = c[i-1][j]b[i][j] = 2else:   #从左方来c[i][j] = c[i][j-1]b[i][j] = 3return c[m][n], bdef lcs_trackback(x, y):c, b = lcs(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 -= 1j -= 1elif b[i][j] == 2:  #来自上方i -= 1else:  #来自左方j -= 1return "".join(reversed(res))x = "ABCBDAB"
y = "BDCABA"
c, b = lcs(x,y)
print(lcs_trackback(x, y))

<可能有多个最长公共子序列>