动态规划的几种典型模型

动态规划是对最优化问题的一种新的算法设计方法。

由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。

不存在一种万能的动态规划算法。

但是可以通过对若干有代表性的问题的动态规划算法进行讨论，学会这一设计方法。

多阶段决策过程最优化问题——动态规划的基本模型在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。

因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。

当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。

这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。

【例题1】最短路径问题。

图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。

现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、 B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。

用dk(x k，x k+1)表示在第k阶段由初始状态x k到下阶段的初始状态x k+1的路径距离，Fk(x k)表示从第k阶段的x k到终点E的最短距离，利用倒推方法求解A到E的最短距离。

具体计算过程如下：S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3S2: K=3，有：F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8F3(C2)=d3(C2,D1)+f4(D1)=5+3=8F3(C3)=d3(C3,D3)+f4(D3)=8+3=11F3(C4)=d3(C4,D3)+f4(D3)=3+3=6S2: K=2，有：F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)}=min {9,12,14}=9F2(m)=min{d2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)}=min{16,10}=10S4：k=1，有：F1(A)=min{d1(A,B1)+F2(B1),d1(A,B2)+F2(B2)}=min{13,13}=13因此由A点到E点的全过程的最短路径为A—>B2一>C4—>D3—>E。

动态规划（2）——常见动态规划模型1.数字三⾓形每次可以往右下或者左下⾛⼀格，求路径的最⼤权值.d(i,j)=max(d(i+1,j),d(i+1,j+1))+a(i,j).边界是d(n+1,j)=0，从下往上推（因为要保证i+1⾏在第i⾏之前更新）for(int i=1;i<=n+1;++i) d[n+1][i]=0;for(int i=n;i>=1;--i){for(int j=1;j<=i;++j){d[i][j]=max(d[i+1][j],d[i+1][j+1])+a[i][j];}}2.嵌套矩形有n个矩形，每个矩形⽤⼀个⼆元组(a,b)表⽰。

我们规定矩形X(a,b)可以嵌套在矩形Y(c,d)中当且仅当a<c,b<d，或者b<c,a<d（旋转了90度）。

选出尽量多的矩形排成⼀⾏，使得除了最后⼀个之外，每个矩形都能嵌套在下⼀个矩形内。

若有多解，保证字典序尽量⼩DAG最长路问题//dp[i]表⽰的是从i点出发的最长路int dp(int x){int &ans=d[x];if(ans) return ans;for(int i=1;i<=n;++i){if(G[x][i]){ans=max(ans,dp(i)+1);//注意记录的是从终点到起点的距离，这是为了⽅便字典序最⼩⽅案的输出}}d[x]=ans;return ans;}void print(int i){printf("%d ",i);for(int j=1;j<=n;++j){if(G[i][j]&&d[j]+1==d[i]){print(j);}}}for(int i=1;i<=n;++i){scanf("%d%d",&a[i],&b[i]);if(a[i]>b[i]) swap(a[i],b[i]);}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(a[i]>a[j]&b[i]>b[j]){G[j][i]=1;}}}int Max=0;int endpos;for(int i=1;i<=n;++i){if(dp(i)>Max){Max=dp[i];endpos=i;}}print(endpos);3.硬币问题f(i)=min(inf,f[i−Vi]+1|Vi<=i),g(i)=max(−inf,g[i−Vi]+1|Vi<=i)(Vi为硬币的⾯值)4.01背包已有专门专题详细讲解5.点集配对问题（状压dp)d(S) 表⽰集合S配对之后的最短距离double dis(int i,int j){return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));}int main(){int n;scanf("%d",&n);for(int i=0;i<n;++i) scanf("%d%d",&a[i].x,&a[i].y);memset(d,0x7f,sizeof(d));d[0]=0;for(int i=1;i<(1<<n);++i)//由于第⼀个点⽆论如何都是要配对的，所以⽆需枚举（否则时间复杂度会{ //乘上⼀个n）int k=0;while(!(i&(1<<k))) ++k;for(int j=k+1;j<n;++j){if(i&(1<<j)) d[i]=min(d[i],d[i^(1<<k)^(1<<j)]+dis(k,j));}}}6.最长上升⼦序列问题（LIS）初级：O(n2) （不过太不优秀了，我学会了第⼆种，就从没⽤过它）进阶：O(nlogn) d[i]表⽰以a[i]结尾的最长上升⼦序列的长度for(int i=1;i<=n;+i) g[i]=inf;for(int i=0;i<n;++i){int k=lower_bound(g+1,g+n+1,a[i])-g;d[i]=k;g[k]=a[i];}7.最长公共⼦序列问题(LCS)[ 注意：LCS有时也指最长公共后缀，与LCP最长公共前缀对应 ]for(int i=0;i<la;++i){for(int j=0;j<lb;++j){if(a[i]==b[j]){d[i][j]=max(d[i][j],d[i-1][j-1]+1);}else if(a[i]!=b[j]){d[i][j]=max(d[i-1][j],d[i][j-1]);}}}还可以滚动数组优化int f=0;for(int i=0;i<la;++i){f^=1;for(int j=0;j<lb;++j){if(a[i]==b[j]){d[f][j]=max(d[f][j],[f^1][j-1]+1);}else if(a[i]!=b[j]){d[f][j]=max(d[f^1][j],d[f][j-1]);}}}8.最⼤连续和前缀和做法：for(int i=1;i<=n;++i){scanf("%d",&a[i]);sum[i]=sum[i-1]+a[i];}int Maxn=sum[n],Max=0;for(int i=n-1;i>=1;--i){Max=max(Max,Maxn-sum[i]);Maxn=max(Maxn,sum[i]);}动态规划做法：d[i]表⽰以i结尾的最⼤连续和for(int i=1;i<=n;++i) scanf("%d",&a[i]);for(int i=1;i<=n;++i){d[i]=max(0,d[i-1])+a[i];}Processing math: 100%。

动态规划动态规划模型的分类：以“时间”角度可分成：离散型和连续型。

从信息确定与否可分成：确定型和随机型。

从目标函数的个数可分成：单目标型和多目标型。

动态规划的基本模型1.多阶段决策过程的最优化问题2.动态规划的基本概念3.最优化原理与无后效性多阶段决策过程的最优化问题在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。

当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如下图所示：最短路径问题。

下图给出了一个地图，地图中的每个顶点代表一个城市，两个城市间的一条连线代表道路，连线上的数值代表道路的长度。

现在想从城市A到达城市E，怎样走路程最短？最短路程的长度是多少？把A到E的全过程分成四个阶段，用K表示阶段变量，第1阶段有一个初始状态A，有两条可供选择的支路A-B1、A-B2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。

用DK（X，X+1）表示在第K 阶段由初始状态X到下阶段的初始状态X+1的路径距离，FK（X）表示从第K阶段的X到终点E的最短距离。

在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计方法。

动态规划的基本概念阶段和阶段变量：用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。

描述阶段的变量称为阶段变量，通常用K表示，阶段的划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多阶段决策过程，如上题中，可将其划分成4个阶段，即K = 1，2，3，4。

动态规划：钢条切割问题问题：Serling公司购买长钢条，将其切割为短钢条出售。

不同的切割⽅案，收益是不同的，怎么切割才能有最⼤的收益呢？假设，切割⼯序本⾝没有成本⽀出。

假定出售⼀段长度为i英⼨的钢条的价格为p i （i=1,2,…）。

钢条的长度为n英⼨。

如下给出⼀个价格表P。

给定⼀段长度为n英⼨的钢条和⼀个价格表P，求切割钢条⽅案，使得销售收益 r n最⼤。

(如果长度为n英⼨的钢条的价格p n ⾜够⼤，则可能完全不需要切割，出售整条钢条是最好的收益)⾃顶向下动态规划算法：1public static int buttom_up_cut(int[] p) {2int[] r = new int[p.length + 1];3for (int i = 1; i <= p.length; i++) {4int q = -1;5//①6for (int j = 1; j <= i; j++)7 q = Math.max(q, p[j - 1] + r[i - j]);8 r[i] = q;9 }10return r[p.length];11 }为什么长度为i时的最⼤收益 r[i] 可以通过注释①处的循环来求呢？假设长度为i时钢条被分割为x段{m1,m2,m3,...,mx}可得最⼤收益 r[i] ，取出其中⼀段mk，则最⼤收益可表⽰为r[i] = p[mk] + r[i - mk]如果r[i - mk] 不是长度为 i - mk 时的最⼤收益的话，则r[i]是长度为i时的最⼤收益也就不成⽴，所以最⼤收益r[i]⼀定可以表⽰成单独切出⼀段的价格p[mk] 加上余下长度的最⼤收益 r[i - mk]以下内容转载⾃： https:///szz715/blog/3103246前⾔众所周知，递归算法时间复杂度很⾼为（2^n），⽽动态规划算法也能够解决此类问题，动态规划的算法的时间复杂度为（n^2）。

动态规划问题常见解法动态规划（Dynamic Programming）是一种常用的算法思想，用于解决一类具有重叠子问题性质和最优子结构性质的问题。

动态规划通常通过将问题划分为若干个子问题，并分别求解子问题的最优解，从而得到原问题的最优解。

以下是动态规划问题常见的解法：1. 斐波那契数列斐波那契数列是动态规划问题中的经典案例。

它的递推关系式为 F(n) = F(n-1) + F(n-2)，其中 F(0) = 0，F(1) = 1。

可以使用动态规划的思想来解决斐波那契数列问题，通过保存已经计算过的子问题的结果，避免重复计算。

2. 背包问题背包问题是一个经典的优化问题，可以使用动态规划的方法进行求解。

背包问题包括 0/1 背包问题和完全背包问题。

0/1 背包问题中每个物品要么被选中放入背包，要么不选。

完全背包问题中每个物品可以被选中多次放入背包。

通过定义状态转移方程和使用动态规划的思想，可以高效地求解背包问题。

3. 最长递增子序列最长递增子序列是一个常见的子序列问题，可以使用动态规划的方法进行求解。

最长递增子序列指的是在一个序列中，找到一个最长的子序列，使得子序列中的元素按照顺序递增。

通过定义状态转移方程和使用动态规划的思想，可以有效地求解最长递增子序列问题。

4. 最长公共子序列最长公共子序列是一个经典的字符串问题，可以使用动态规划的方法进行求解。

给定两个字符串，找到它们之间最长的公共子序列。

通过定义状态转移方程和使用动态规划的思想，可以高效地求解最长公共子序列问题。

5. 矩阵链乘法矩阵链乘法是一个求解最优括号化问题的经典案例，可以使用动态规划的方法进行求解。

给定多个矩阵的大小，需要找到一个最优的计算顺序，使得计算乘积的次数最少。

通过定义状态转移方程和使用动态规划的思想，可以高效地求解矩阵链乘法问题。

以上是动态规划问题的常见解法，通过使用动态规划的思想和方法，可以解决这些问题，并求得最优解。

例谈四种常见的动态规划模型动态规划是解决多阶段决策最优化问题的一种思想方法，本文主要结合一些例题，把一些常见的动态规划模型，进行归纳总结。

（一）、背包模型可用动态规划解决的背包问题，主要有01背包和完全背包。

对于背包的类型，这边就做个简单的描述：n个物品要放到一个背包里，背包有个总容量m，每个物品都有一个体积w[i]和价值v[i]，问如何装这些物品,使得背包里放的物品价值最大。

这类型的题目，状态表示为：f[j]表示背包容量不超过j时能够装的最大价值，则状态转移方程为：f[j]:=max{f[j-w[i]]+v[i]},边界：f[0]:=0;简单的程序框架为：beginreadln(m,n);for i:=1 to n do readln(w[i],v[i]);f[0]:=0;for i:=1 to m dofor j:=1 to n dobeginif i>=w[j] then t:=f[i-w[j]]+v[j];if t>f[i] then f[i]:=t;end;writeln(f[m]);end.这类型的题目应用挺广的（noip1996提高组第4题，noip2001普及组装箱问题，noip2005普及组采药等），下面一个例子，也是背包模型的简单转化。

货币系统(money)【问题描述】母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。

他们对货币的数值感到好奇。

传统地，一个货币系统是由1，5，10，20或25，50，100的单位面值组成的。

母牛想知道用货币系统中的货币来构造一个确定的面值，有多少种不同的方法。

使用一个货币系统{1,2,5,10,..}产生18单位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。

写一个程序来计算有多少种方法用给定的货币系统来构造一个确定的面值。

【输入格式】货币系统中货币的种类数目是v(1≤v≤25)；要构造的面值是n(1≤n≤10,000)；第1行:二个整数，v和n；第2..v+1行：可用的货币v个整数(每行一个)。