45道动态规划题目分析

动态规划练习题[题1] 多米诺骨牌（DOMINO）问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。

现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。

顶行和底行的差值是2。

这个差值是两行点数之和的差的绝对值。

每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。

现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。

对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

输入格式：文件的第一行是一个整数n（1〈=n〈=1000〉，表示有n个多米诺骨牌在桌面上排成一行。

接下来共有n行，每行包含两个整数a、b（0〈=a、b〈=6，中间用空格分开〉。

第I+1行的a、b分别表示第I个多米诺骨牌的上部与下部的点数（0表示空）。

输出格式：只有一个整数在文件的第一行。

这个整数表示翻动骨牌的最少次数，从而使得顶行和底行的差值最小。

[题2] Perform巡回演出题目描述:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出).由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同.现要求寻找一张花费费用最小的演出表.输入: 输入文件包括若干个场景.每个场景的描述由一对整数n(2<=n<=10)和k(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组n-1份航班表对应从城市1到其他城市(2,3,...n)的航班,接下的n-1行是从城市2到其他城市(1,3,4...n)的航班,如此下去.每份航班又一个整数d(1<=d<=30)开始,表示航班表循环的周期,接下来的d个非负整数表示1,2...d天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"3 75 0 80"表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.样例输入: 样例输出：3 6 4602 130 150 03 75 0 807 120 110 0 100 110 120 04 60 70 60 503 0 135 1402 70 802 32 0 701 800 0[题3] 复制书稿（BOOKS）问题描述：假设有M本书（编号为1，2，…M），想将每本复制一份，M本书的页数可能不同（分别是P1，P2，…PM）。

动态规划的具体应用例题3.1 最长不降子序列（1）问题描述设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j)例如3，18，7，14，10，12，23，41，16，24。

若存在i1<i2<i3< … < ie 且有a(i1)<a(i2)< … <a(ie)则称为长度为e的不下降序列。

如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。

程序要求，当原数列给出之后，求出最长的不下降序列。

（2）算法分析根据动态规划的原理，由后往前进行搜索。

1· 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；2· 若从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)。

3· 一般若从a(i)开始，此时最长不下降序列应该按下列方法求出: 在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。

4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继接点的编号(3) 程序如下:（逆推法）program li1;const maxn=100;var a,b,c:array[1..maxn] of integer;fname:string;f:text;n,i,j,max,p:integer;beginreadln(fname);assign(f,fname);reset(f);readln(f,n);+for i:=1 to n dobeginread(f,a[i]);b[n]:=1;c[n]:=0;end;for i:= n-1 downto 1 dobeginmax:=0;p:=0;for j:=i+1 to n doif (a[i]<a[j]) and (b[j]>max) then begin max:=b[j];p:=j end;if p<>0 then begin b[i]:=b[p]+1;c[i]:=p endend;max:=0;p:=0;for i:=1 to n doif b[i]>max then begin max:=b[i];p:=i end;writeln('maxlong=',max);write('result is:');while p<>0 dobegin write(a[p]:5);p:=c[p] end;end.3.2 背包问题背包问题有三种1.部分背包问题一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。

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

该方法是由美国数学家贝尔曼(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. 0/1背包问题0/1背包问题是动态规划中的经典问题，解决的是在背包容量固定的情况下，如何选择物品放入背包，使得总价值最大化。

常见的解法有两种：记忆化搜索和动态规划。

记忆化搜索是一种自顶向下的解法，通过保存子问题的解来避免重复计算，提高效率。

动态规划是一种自底向上的解法，通过填表格的方式记录每个子问题的解，最终得到整个问题的最优解。

2. 完全背包问题完全背包问题是在背包容量固定的情况下，如何选择物品放入背包，使得总价值最大化，且每种物品可以选择任意个。

常见的解法有两种：记忆化搜索和动态规划。

记忆化搜索和动态规划的思路和0/1背包问题相似，只是在状态转移方程上有所不同。

二、最长公共子序列问题最长公共子序列问题是指给定两个序列，求它们之间最长的公共子序列的长度。

常见的解法有两种：递归和动态规划。

递归的思路是通过分别考虑两个序列末尾元素是否相等来进一步缩小问题规模，直至问题规模减小到边界情况。

动态规划的思路是通过填表格的方式记录每个子问题的解，最终得到整个问题的最优解。

三、最短路径问题最短路径问题是指在加权有向图或无向图中，求解从一个顶点到另一个顶点的最短路径的问题。

常见的解法有两种：Dijkstra算法和Bellman-Ford算法。

Dijkstra算法是通过维护一个距离表，不断选择距离最短的顶点来更新距离表，直至找到目标顶点。

Bellman-Ford算法是通过进行多次松弛操作，逐步缩小问题规模，直至找到目标顶点或发现负权环。

总结：动态规划是一种解决最优化问题的常见方法，它通过分组子问题、定义状态、确定状态转移方程和填表格的方式，来得到整个问题的最优解。

在解决动态规划问题时，可以采用记忆化搜索或者动态规划的策略，具体选择哪种方法可以根据问题的特点和优化的需要来决定。

常见动态规划题⽬详解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。