动态规划经典题目分析共37页文档

动态规划动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种方法。

该方法是由美国数学家贝尔曼(R．Bellman)等人在本世纪50年代初提出的。

他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多实际问题，从而建立了运筹学的一个新分支——动态规划。

他的名著《动态规划》于1957年出版，该书是动态规划的第一本著作。

动态规划是现代企业管理中的一种重要决策方法，在工程技术、经济管理、工农业生产及军事及其它部们都有广泛的应用，并且获得了显著的效果。

动态规划可用于解决最优路径问题、资源分配问题、生产计划与库存问题、投资分配问题、装载问题、设备更新与维修问题、排序问题及生产过程的最优控制等。

由于它所具有独特的解题思路，在处理某些优化问题时，常常比线性规划或非线性规划方法更有效。

第一节动态规划的基本方法多阶段决策的实际问题很多，下面通过具体例子，说明什么是动态规划模型及其求解方法。

例1：最短路线问题某工厂需要把一批货物从城市A运到城市E，中间可经过B1 、B2、B3、C1、C2、C3、D1、D2等城市，各城市之间的交通线和距离如下图所示，问应该选择一条什么路线，使得从A到E的距离最短？下面引进几个动态规划的基本概念和相关符号。

(1)阶段(Stage)把所给问题的过程，按时间和空间特征划分成若干个相互联系的阶段，以便按次序去求每个阶段的解，阶段总数一般用字母n表示，用字母k表示阶段变量。

如例l中 (最短路线问题)可看作是n=4阶段的动态规划问题，k=2表示处于第二阶段。

(2)状态(State)状态表示每个阶段开始时系统所处的自然状况或客观条件，它描述了研究问题过程状况。

描述各阶段状态的变量称为状态变量，常用字母sk表示第k阶段的状态变量，状态变量的取值范围称为状态集，用Sk表示。

如例l中，第一阶段的状态为A（即出发位置）。

第二阶段有三个状态：B1 、B2、B3，状态变量s2=B2表示第2阶段系统所处的位置是B2。

动态规划总结——经典问题总结本文着重讨论状态是如何表示，以及方程是怎样表示的。

当然，还附上关键的，有可能作为模板的代码段。

但有的代码的实现是优化版的。

经典问题总结最长上升子序列（LIS）问题描述如下:设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>，其中k1<k2<…<km且aK1<ak2<…<akm。

求最大的m值。

这里采用的是逆向思维的方法，从最后一个开始想起，即先从A[N]（A数组是存放数据的数组，下同）开始，则只有长度为1的子序列，到A[N-1]时就有两种情况，如果a[n-1] < a[n] 则存在长度为2的不下降子序列a[n-1],a[n]；如果a[n-1] > a[n] 则存在长度为1的不下降子序列a[n-1]或者a[n]。

有了以上的思想，DP方程就呼之欲出了（这里是顺序推的，不是逆序的）：DP[I]=MAX（1,DP[J]+1）J=0,1,...,I-1但这样的想法实现起来是）O(n^2)的。

本题还有更好的解法，就是O(n*logn)。

利用了长升子序列的性质来优化，以下是优化版的代码：//最长不降子序const int SIZE=500001;int data[SIZE];int dp[SIZE];//返回值是最长不降子序列的最大长度,复杂度O(N*logN)int LCS(int n) { //N是DATA数组的长度,下标从1开始int len(1),low,high,mid,i;dp[1]=data[1];for(i=1;i<=n;++i) {low=1;high=len;while( low<=high ) { //二分mid=(low+high)/2;if( data[i]>dp[mid] ) {low=mid+1;}else {high=mid-1;}}dp[low]=data[i];if( low>len ) {++len;}}return len;}最长公共子序列（LCS）给出两个字符串a, b，求它们的最长、连续的公共字串。

动态规划算法详解及经典例题⼀、基本概念（1）⼀种使⽤多阶段决策过程最优的通⽤⽅法。

（2）动态规划过程是：每次决策依赖于当前状态，⼜随即引起状态的转移。

⼀个决策序列就是在变化的状态中产⽣出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

假设问题是由交叠的⼦问题所构成，我们就能够⽤动态规划技术来解决它。

⼀般来说，这种⼦问题出⾃对给定问题求解的递推关系中，这个递推关系包括了同样问题的更⼩⼦问题的解。

动态规划法建议，与其对交叠⼦问题⼀次重新的求解，不如把每⼀个较⼩⼦问题仅仅求解⼀次并把结果记录在表中（动态规划也是空间换时间的）。

这样就能够从表中得到原始问题的解。

（3）动态规划经常常使⽤于解决最优化问题，这些问题多表现为多阶段决策。

关于多阶段决策：在实际中，⼈们经常遇到这样⼀类决策问题，即因为过程的特殊性，能够将决策的全过程根据时间或空间划分若⼲个联系的阶段。

⽽在各阶段中。

⼈们都须要作出⽅案的选择。

我们称之为决策。

⽽且当⼀个阶段的决策之后，经常影响到下⼀个阶段的决策，从⽽影响整个过程的活动。

这样，各个阶段所确定的决策就构成⼀个决策序列，常称之为策略。

因为各个阶段可供选择的决策往往不⽌⼀个。

因⽽就可能有很多决策以供选择，这些可供选择的策略构成⼀个集合，我们称之为同意策略集合（简称策略集合）。

每⼀个策略都对应地确定⼀种活动的效果。

我们假定这个效果能够⽤数量来衡量。

因为不同的策略经常导致不同的效果，因此，怎样在同意策略集合中选择⼀个策略，使其在预定的标准下达到最好的效果。

经常是⼈们所关⼼的问题。

我们称这种策略为最优策略，这类问题就称为多阶段决策问题。

（4）多阶段决策问题举例：机器负荷分配问题某种机器能够在⾼低两种不同的负荷下进⾏⽣产。

在⾼负荷下⽣产时。

产品的年产量g和投⼊⽣产的机器数量x的关系为g=g(x)，这时的年完善率为a，即假设年初完善机器数为x，到年终时完善的机器数为a*x(0<a<1)；在低负荷下⽣产时，产品的年产量h和投⼊⽣产的机器数量y的关系为h=h(y)。

动态规划算法详解及经典例题动态规划什么是动态规划？动态规划的⼤致思路是把⼀个复杂的问题转化成⼀个分阶段逐步递推的过程，从简单的初始状态⼀步⼀步递推，最终得到复杂问题的最优解。

基本思想与策略编辑:由于动态规划解决的问题多数有重叠⼦问题这个特点，为减少重复计算，对每⼀个⼦问题只解⼀次，将其不同阶段的不同状态保存在⼀个⼆维数组中。

1. 拆分问题：根据问题的可能性把问题划分成通过递推或者递归⼀步⼀步实现。

关键就是这个步骤,动态规划有⼀类问题就是从后往前推到,有时候我们很容易知道 : 如果只有⼀种情况时,最佳的选择应该怎么做.然后根据这个最佳选择往前⼀步推导,得到前⼀步的最佳选择 2. 定义问题状态和状态之间的关系：⽤⼀种量化的形式表现出来,类似于⾼中学的推导公式,因为这种式⼦很容易⽤程序写出来,也可以说对程序⽐较亲和(也就是最后所说的状态转移⽅程式) 3. 动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若⼲个⼦问题（阶段），按顺序求解⼦阶段，前⼀⼦问题的解，为后⼀⼦问题的求解提供了有⽤的信息。

在求解任⼀⼦问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。

依次解决各⼦问题，最后⼀个⼦问题就是初始问题的解。

我的理解是：⽐如我们找到最优解,我们应该讲最优解保存下来,为了往前推导时能够使⽤前⼀步的最优解,在这个过程中难免有⼀些相⽐于最优解差的解,此时我们应该放弃,只保存最优解,这样我们每⼀次都把最优解保存了下来,⼤⼤降低了时间复杂度。

动态规划解决问题的过程分为两步：1.寻找状态转移⽅程式2.利⽤状态转移⽅程式⾃底向上求解问题动态规划原理使⽤条件：可分为多个相关⼦问题，⼦问题的解被重复使⽤使⽤条件：可分为多个相关⼦问题，⼦问题的解被重复使⽤Optimal substructure（优化⼦结构）：⼀个问题的优化解包含了⼦问题的优化解缩⼩⼦问题集合，只需那些优化问题中包含的⼦问题，降低实现复杂性我们可以⾃下⽽上的Subteties（重叠⼦问题）：在问题的求解过程中，很多⼦问题的解将被多次使⽤。

动态规划解析第一题导弹拦截本题第一问实际上是给出数列a1..a n,求最长非递增序列的长度，{容易想到以n来划分子问题，即分别求a1..a n-1, a1..a n-2, …, a1,中最长非递增序列长度，但各级子问题之间不易建立转化关系}将子问题具体一些，我们可以用f[k]表示数列a1..a k中以a k结尾的最长非递增序列的长度，题目所求即为max{f[1..n]}。

转移方程为f[n]=max{f[k]}+1;(0<=k<n,a[n]<=a[k] )设a[0]= -maxint,f[0]=0;第二问可以用贪心做，设拦截前k个导弹用o2个系统，其最后拦截的高度分别为l[1]..l[o2],则拦截第k+1个导弹时，找能够拦截这枚导弹的系统中最后拦截高度最小的，若没有这样的系统则新增一个系统。

附源程序：const max = 10000;type arr = array[0..max]of integer;var d,l : arr;i,j,k,m,n,o1,o2,t : longint;procedure input;beginfillchar(d,sizeof(d),0);fillchar(l,sizeof(l),0);writeln('input:');i:=0;repeati:=i+1;read(d[i]);until eoln;t:=i;o1:=0; o2:=0;end;procedure output;beginwriteln('Output:');writeln(o1);writeln(o2);end;procedure main1;beginl[t]:=1;for i:=t-1 downto 1 do begink:=0;for j:=i+1 to t doif (l[j]>k)and(d[i]>=d[j]) then k:=l[j];l[i]:=k+1;end;for i:=1 to t doif l[i]>o1 then o1:=l[i];end;procedure main2;beginfor i:=0 to t do l[i]:=maxint;o2:=1;for i:=1 to t do begink:=0;for j:=1 to o2 doif (l[j]>=d[i])and(l[j]<=l[k]) then k:=j;if k=0 then begino2:=o2+1;k:=o2;end;l[k]:=d[i];end;end;begininput;main1;main2;output;end.第二题 石子合并设f[i,j](i<=j)表示将第i 堆到第j 堆石子合并为一堆所得的最大分数（最小时类似）。

常见动态规划题⽬详解1.爬楼梯题⽬描述：假设你正在爬楼梯。

需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。

你有多少种不同的⽅法可以爬到楼顶呢？注意：给定 n 是⼀个正整数。

⽰例 1：输⼊： 2输出： 2解释：有两种⽅法可以爬到楼顶。

1. 1 阶 + 1 阶2. 2 阶⽰例 2：输⼊： 3输出： 3解释：有三种⽅法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶2. 1 阶 + 2 阶3. 2 阶 + 1 阶实现代码：class Solution {public:int climbStairs(int n) {vector<int> a(n);a[0] = 1;a[1] = 2;if(n == 1){return 1;}if(n == 2){return 2;}for(int i = 2; i < n;i++){a[i] = a[i - 1] + a[i - 2];}return a[n - 1];}};2.变态跳台阶题⽬描述：⼀只青蛙⼀次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。

求该青蛙跳上⼀个n级的台阶总共有多少种跳法。

实现代码：class Solution {public:int jumpFloorII(int number) {if(number == 0){return 0;}int total = 1;for(int i = 1; i < number; i++){total *= 2;}return total;}};3.n年后⽜的数量题⽬描述：假设农场中的母⽜每年会产⽣⼀头⼩母⽜，并且永远不会死。

第⼀年农场中只有⼀头成熟的母⽜，第⼆年开始，母⽜开始⽣⼩母⽜，每只⼩母⽜三年之后成熟⼜可以⽣⼩母⽜，给定整数N，求N年后母⽜的数量。

实现代码：class solution{　public: int f(int n){ if(n < 1){ return 0; } if(n == 1|| n== 2||n == 3){ return n; } int res = 3; int pre = 2; int prepre = 1; int tmp1=0; int tmp2 = 0; for(int i = 4;i < n;i++){ tmp1 = res; tmp2 = pre; res = pre + prepre; pre = tmp1; prepre = tmp2; } return res; }};4.矩形覆盖题⽬描述：我们可以⽤2*1的⼩矩形横着或者竖着去覆盖更⼤的矩形。

几个经典的动态规划问题动态规划复习：《便宜的旅行》分析：这个问题很明显是一个动态规划的标准问题。

考虑某一天晚上车队到达了终点，上一次的花销必然是只与早上车队所在的位置有关的。

这样，由于要求从起点到终点最优的方案，所以从起点到达早上所出发时旅馆的方案也应该是最优的。

以此类推，我们可以得出我们应该求出从起点到各个旅馆的最优方案。

这样，如果我们设从起点到旅馆s i∈S (1≤ i≤ n)的最优方案的价值为f(s i)，就可以得到如下的动态规划方程：F(s[i])=min{f(s[j])}+value[i];0<=s[i]-s[j]<=800这里value(s i)为s i的价值。

《蛙人》设F(i,j) 是携带i升氧气，j升氮气的最小重量F(i+a k,j+t k)=min{f(i,j)+W k}李曙华同学程序for i:=0 to 21 dofor j:=0 to 79 doa[i,j]:=10000000;a[0,0]:=0;for i:=1 to n dobeginreadln(b[i,1],b[i,2],b[i,3]);for j:=21-b[i,1] downto 0 dofor k:=79-b[i,2] downto 0 dobeginif a[j,k]>a[j,k+1] then a[j,k]:=a[j,k+1];if a[j,k]>a[j+1,k] then a[j,k]:=a[j+1,k];if a[j+b[i,1],k+b[i,2]]>a[j,k]+b[i,3] thena[j+b[i,1],k+b[i,2]]:=a[j,k]+b[i,3];end;end;writeln(a[x,y]);close(input);close(output);end.几个经典的动态规划问题一、背包问题：在M件物品取出若干件放在空间为W的背包里，每件物品的重量为W1，W·2……Wn，与之相对应的价值为P1,P2……Pn。

动态规划经典问题1、三角数塔问题设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。

从顶点出发，可以向左走或向右走，如图所示：要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。

【代码】//// 例题1 三角数字塔问题////#include <stdio.h>#include <stdlib.h>#define MAXN 101intn,d[MAXN][MAXN];int a[MAXN][MAXN];voidfnRecursive(int,int);//递推方法函数声明intfnMemorySearch(int,int);//记忆化搜索函数声明int main(){inti,j;printf("输入三角形的行数n(n=1-100):\n");scanf("%d",&n);printf("按行输入数字三角形上的数(1-100):\n");for(i=1; i<=n; i++)for(j=1; j<=i; j++)scanf("%d",&a[i][j]);for(i=1; i<=n; i++)for(j=1; j<=i; j++)d[i][j]=-1;//初始化指标数组printf("递推方法：1\n记忆化搜索方法：2\n");int select;scanf("%d",&select);if(select==1){fnRecursive(i,j);//调用递推方法printf("\n%d\n",d[1][1]);}if(select==2){printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法}elseprintf("输入错误！");return 0;}voidfnRecursive(inti,int j)//递推方法实现过程{for(j=1; j<=n; j++)d[n][j]=a[n][j];for(i=n-1; i>=1; i--)for(j=1; j<=i; j++)d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]); }intfnMemorySearch(inti,int j)//记忆化搜索实现过程{if(d[i][j]>=0) return d[i][j];if(i==n) return(d[i][j]=a[i][j]);if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1))return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));elsereturn(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));}2、硬币问题问题描述：有n种硬币，面值分别为V1,V2,…,Vn, 每种有无限多。

力扣优秀题解——动态规划动态规划（Dynamic programming，简称DP）是一种常见的求解优化问题的方法。

它与分治算法类似，都是通过将大问题分解成若干个小问题来求解的。

不同的是，DP解决的问题通常是有重叠子问题和最优子结构特征的，即在求解过程中会反复计算相同的子问题，并且每个子问题都具有最优解，可以通过这些最优解推导出全局最优解。

力扣中的很多题目都可以使用动态规划来解决，比如最长公共子序列、股票买卖、打家劫舍等等。

下面针对这些题目进行详细解析。

一、最长公共子序列题目描述：给定两个字符串text1 和text2，返回它们的最长公共子序列。

如果不存在公共子序列，返回0。

示例：输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace"，它的长度为 3。

解题思路：最长公共子序列问题是比较经典的DP问题。

设字符串text1和text2的长度分别为m 和n，令dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度，为方便起见，text1和text2的下标从1开始。

当text1[i-1] == text2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1，即text1[0:i-1]和text2[0:j-1]的最长公共子序列长度加上1。

当text1[i-1] != text2[j-1]时，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，即考虑text1[0:i-1]和text2[0:j]的最长公共子序列长度与text1[0:i]和text2[0:j-1]的最长公共子序列长度，两者取最大值。

最终的答案即为dp[m][n]。

代码实现：class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]二、股票买卖题目描述：给定一个数组prices，其中prices[i]是一支给定股票第i天的价格。