题记

动态规划是蓝桥杯常考的题型，同时也是建模常考的规划。但是我翻了一些博客，我发现很少有用Python实现。所以，参照几篇博客进行总结和归纳后，我整理出来了全面的动态规划使用场景+代码。

动态规划是什么？

看一遍就理解：动态规划详解 - 云+社区 - 腾讯云 (tencent.com)

这位大佬写的真的通俗易懂，方便大家理解。文中涉及的代码转换成Python代码如下：

 线性规划的分类及代表问题

线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；

区域动规：石子合并，加分二叉树，统计单词个数，炮兵布阵等；

树形动规：贪吃的九头龙，二分查找书，聚会的欢乐，数字三角形等；

背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等；

应用实例：最短路径问题，项目管理，网络流优化等。

 一、线性动归

 1.青蛙跳阶

青蛙跳阶-递归

def numWays(n):    if n==1:        return 1    elif n==2:        return 2    else:        return numWays(n-1)+numWays(n-2)n=eval(input())print(numWays(n)%1000000007)

青蛙跳阶-带备忘录的递归

lt=[1,2]for i in range(2,n):    lt.append(lt[i-1]+lt[i-2])n=eval(input())print(lt[n-1]%1000000007)

青蛙跳阶-自底向上的动态规划

a,b=1,2n=eval(input())for i in range(2,n):    a,b=b,(a+b)%1000000007print(b)

2.穷举分析

s=input()#输入格式x1,x2,x3,...ls=list(map(int,s.split(',')))n=len(ls)dp=[1 for i in range(n)]maxlen=1for i in range(n):    for j in range(0,i):        if ls[i]>ls[j]:            dp[i]=max(dp[i],dp[j]+1)    maxlen=max(maxlen,dp[i])print(maxlen)print(dp)

结果： （和博客中分析结果一致）

 分析：这道题看起来真的挺难的，但是如果正确分析，就会发现其实这道题的代码很简单。所以这个题的解决思路要重点关注。

3.钢条切割

题目和分析见这篇博客的[动态规划小试牛刀]

算法-动态规划 Dynamic Programming--从菜鸟到老鸟_HankingHu的博客-CSDN博客_动态规划

钢条切割-递归

value=[0,1,5,8,9,10,17,17,20,24,30]length=list(range(0,11))#定义价格和长度def cutmax(n):    if n<=0:        return 0    elif n==1:        return 1    else:        q=value[n]        for i in range(1,n):            q=max(q,cutmax(i)+cutmax(n-i))        return qx=eval(input())print(cutmax(x))

钢条切割-备忘录

这道题的备忘录方法没什么意思，备忘录方法无非是在递归的时候记录下已经调用过的子函数的值。过程：定义函数-->循环调用函数+保存结果，代码太长太冗余了，直接学习动态规划方法吧。

钢条切割-自底向上的动态规划

value=[0,1,5,8,9,10,17,17,20,24,30]x=eval(input())valuemax=value.copy()if x>10:    valuemax+=[0]*(x-10)for i in range(1,x+1):    for j in range(1,i):        valuemax[i]=max(valuemax[i],valuemax[j]+valuemax[i-j])print(valuemax[x])

4.合唱队形问题

动态规划——合唱队 - Achilles_Heel - 博客园 (cnblogs.com)

这个博客也是用Python写的，我改进了一下。

问题补充：（我一开始的疑问）

问题分析中有这样的描述：（第i位同学被重复计算了一次），但是同样存在第i位同学不被重复计算的情况（如下图），这时-1就使合唱人数变小。但是我发现这时的升序人数+降序人数一定小于i取i-1或者i+1时：i=i+1时，升序=4，降序=3；i=i时，升序=3，降序=3。所以虽然当等于i时计算结果有误，但是不会影响最大值的选取。

 在3.穷举分析的代码基础上写代码（对照答案结果一样）

s=input()#输入格式x1,x2,x3,...ls=list(map(int,s.split(',')))n=len(ls)up=[1 for i in range(n)]down=[1 for i in range(n)]for i in range(n):    for j in range(0,i):        if ls[i]>ls[j]:            up[i]=max(up[i],up[j]+1)        if ls[n-i-1]>ls[n-j-1]:            down[n-i-1]=max(down[n-i-1],down[n-j-1]+1)maxlen=[]for k in range(n):    maxlen.append(n-(up[k]+down[k])+1)print(min(maxlen))print(up)print(down)print(maxlen)

 二、区域动归

1.石子合并

动态规划之合并石子_Zekary的博客-CSDN博客_石子合并问题c语言

解法非常清晰，代码转成Python代码如下。

目标方程：minCost [ i ] [ i + k - 1] = min(minCost[ i ][ j ] + minCost[j + 1][ i + k - 1] + theCost)来源【算法笔记】区域型动态规划_石子并归_小宋今天要早睡的博客-CSDN博客_区域动态规划

s=input() #输入格式x1,x2,x3,...ls=list(map(int,s.split(',')))n=len(ls)summ=[]for i in range(n):    t=[]    for j in range(n):        if j<i:            t.append(0)        elif j==i:            t.append(ls[i])        else:            t.append(t[j-1]+ls[j])    summ.append(t)dp=[[0 for i in range(n)] for j in range(n)]for i in range(n):    if i<n-1:        dp[i][i+1]=ls[i]+ls[i+1]for t in range(2,n+1):    for i in range(n-t):        a=dp[i][i+t-1]+summ[i][i+t]        b=dp[i+1][i+t]+summ[i][i+t]        for j in range(1,t-1):            b=min(b,dp[i][i+j]+dp[i+j+1][i+t]+summ[i][i+t])        dp[i][t+i]=min(a,b)print(dp[0][n-1])

 2.加分二叉树

自从计算机二级开始我就对二叉树充满畏惧感，一开始碰到这道题也是完全不想看的状态，但是这种题还挺多的，之前碰到什么左孩子右兄弟也是完全不会做。。。所以这道题我要克服恐惧！

【题解】加分二叉树_Fool-Fish的博客-CSDN博客

这篇博客就是我的学习内容，内容很清晰，而且排版令人很舒服。

def p(L,r):    if L>r:        return    print(root[L][r],end=' ')    if L==r:        return    p(L,root[L][r]-1)    p(root[L][r]+1,r)   #输出根节点函数    n=eval(input())s=input()a=[0]+list(map(int,s.split()))dp=[[0 for i in range(n+1)] for j in range(n+1)]    #用来保存节点的得分root=[[0 for i in range(n+1)] for j in range(n+1)]  #用来保存i,j的共同的根节点for i in range(1,n+1):    dp[i][i]=a[i]    dp[i][i-1]=1    root[i][i]=i  #构造初始的数据for len in range(1,n):    for L in range(1,n-len+1):        r=L+len        dp[L][r]=dp[L+1][r]+a[L]        root[L][r]=L        #print('len,L,r=',len,L,r)        for k in range(L+1,r):            if dp[L][r]<dp[L][k-1]*dp[k+1][r]+a[k]:                dp[L][r]=dp[L][k-1]*dp[k+1][r]+a[k]  #取最大得分                root[L][r]=k print(dp[1][n])p(1,n)

结果：

 从图中可以看出来计算分数一步一步的过程，结果相同。代码在题库中测试，百分百通过。

 三、树形动态规划

1.贪吃的九头龙

【NOI2002】贪吃的九头龙_SSLGZ_yyc的博客-CSDN博客

【这里看起来比较难，待补充】【最近要期中考试了，之后再补】

四、背包问题

1. 01背包

01背包问题详解（浅显易懂）_Iseno_V的博客-CSDN博客_01背包问题详解

背包问题的小试牛刀，这个比较容易，讲的也很详细，懂了这个之后复杂的背包问题就比较容易懂了。

n=eval(input())V=eval(input())s1=input()  #w1,w2,w3,...w=[0]+list(map(int,s1.split(',')))s2=input()  #v1,v2,v3,...v=[0]+list(map(int,s2.split(',')))f=[0 for i in range(V+1)]for i in range(1,n+1):    for j in range(V,w[i]-1,-1):        f[j]=max(f[j],f[j-w[i]]+v[i])print(f[V])

2.背包九讲

dd大牛的《背包九讲》 - 知乎 (zhihu.com)

这个比较完整，讲解也比较详细易懂，也比较长，但是没有题目和代码。

背包九讲----整理+例题_smiling~的博客-CSDN博客_背包九讲

这个讲解不那么详细，但是最重要的dp方程都给出来了。如果前面的代码都跟着我一起学习过一遍了，思路也不需要讲的那么详细其实也可以明白了。所以这个也推荐看，但是代码是C++，后续陆续补充其中代码。【两个博客可以对照学习，代码可以来参照我的代码】

我直接用acwing的题库测试代码，通过的代码会放在这里。

注意一下，acwing网站里的Python编译器是Python2.x版本的，所以有些地方会莫名其妙报错，所以有些函数要稍微改一下。比如：input-->raw_input 

 1.01背包：acwing02 2. 01背包问题 - AcWing题库

n,V=map(int,raw_input().split(' '))w=[0];v=[0]for i in range(n):    t1,t2=map(int,raw_input().split(' '))    w.append(t1)    v.append(t2)f=[0 for i in range(V+1)]for i in range(1,n+1):    for j in range(V,w[i]-1,-1):        f[j]=max(f[j],f[j-w[i]]+v[i])    #print('i=',i,'\t','f=',f)print(f[V])

 

 输出一下结果可以清晰的看到往背包里加入物品的过程。

2. 完全背包：acwing03 3. 完全背包问题 - AcWing题库

n,V=map(int,raw_input().split())w=[0];v=[0]for i in range(n):    t1,t2=map(int,raw_input().split())    w.append(t1)    v.append(t2)f=[0 for i in range(V+1)]for i in range(1,n+1):    for j in range(w[i],V+1):        f[j]=max(f[j],f[j-w[i]]+v[i])    #print('i=',i,'\t','f=',f)print(f[V])

3.多重背包：

【先写到这，待补充】