网站后台用什么做,手机端尺寸,wordpress 栏目设置,福州p2p网站建设公司目录
#xff08;一#xff09;递归到动规的一般转化方法
#xff08;二#xff09;动规解题的一般思路
1. 将原问题分解为子问题
2. 确定状态
3. 确定一些初始状态#xff08;边界状态#xff09;的值
4. 确定状态转移方程
#xff08;三#xff09;能用动规解…
目录
一递归到动规的一般转化方法
二动规解题的一般思路
1. 将原问题分解为子问题
2. 确定状态
3. 确定一些初始状态边界状态的值
4. 确定状态转移方程
三能用动规解决的问题的特点
1.最优子结构
2.无后效性
四动归的常用两种形式
1递归型
2递推型
五例题
数字三角形
题目
解题思路
题目解答
运行该程序会超时为什么呢
递归改递推
空间优化 最长上升子序列
题目
解题思路
1.找子问题
2. 确定状态
3. 找出状态转移方程
题目解答 公共子序列
题目
解题思路
题目解答 一递归到动规的一般转化方法 递归函数有n个参数就定义一个n维的数组数组的下标是递归函数参数的取值范围数组元素的值是递归函数的返回值这样就可以从边界值开始逐步填充数组相当于计算递归函数值的逆过程。
二动规解题的一般思路 1. 将原问题分解为子问题 把原问题分解为若干个子问题子问题和原问题形式相同或类似只不过规模变小了。子问题都解决原问题即解决(数字三角形例。 子问题的解一旦求出就会被保存所以每个子问题只需求解一次。
2. 确定状态 在用动态规划解题时我们往往将和子问题相关的各个变量的一组取值称之为一个“状态”。一个“状态”对应于一个或多个子问题所谓某个“状态”下的“值”就是这个“状态”所对应的子问题的解。 用动态规划解题经常碰到的情况是K个整型变量能构成一个状态如数字三角形中的行号和列号这两个变量构成“状态”。如果这K个整型变量的取值范围分别是N1, N2, ……Nk那么我们就可以用一个K维的数组array[N1] [N2]……[Nk]来存储各个状态的“值”。这个“值”未必就是一个整数或浮点数可能是需要一个结构才能表示的那么array就可以是一个结构数组。一个 “状态”下的“值”通常会是一个或多个子问题的解。
3. 确定一些初始状态边界状态的值 以“数字三角形”为例初始状态就是底边数字值就是底边数字值。
4. 确定状态转移方程 定义出什么是“状态”以及在该 “状态”下的“值”后就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”求出另一个“状态”的“值”(“人人为我”递推型)。状态的迁移可以用递推公式表示此递推公式也可被称作“状态转移方程”。
三能用动规解决的问题的特点 1.最优子结构 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的我们就称该问题具有最优子结构性质。
2.无后效性 无后效性。当前的若干个状态值一旦确定则此后过程的演变就只和这若干个状态的值有关和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态没有关系。
四动归的常用两种形式 1递归型 优点直观容易编写 缺点可能会因递归层数太深导致爆栈函数调用带来额外时间开销。无法使用滚动数组节省空间。总体来说比递推型慢。
2递推型 效率高有可能使用滚动数组节省空间
五例题
数字三角形 题目 图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径把路径上面的数加起来可以得到一个和你的任务就是找到最大的和。 注意路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
输入 输入的是一行是一个整数N (1 N 100)给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出 输出最大的和。
30
解题思路 用二维数组存放数字三角形。 D( r, j) : 第r行第 j 个数字(r,j从1开始算) MaxSum(r, j) : 从D(r,j)到底边的各条路径中 最佳路径的数字之和。 问题求 MaxSum(1,1) 典型的递归问题。 D(r, j)出发下一步只能走D(r1,j)或者D(r1, j1)。故对于N行的三角形 if ( r N) MaxSum(r,j) D(r,j) else MaxSum( r, j) Max{ MaxSum(r1,j), MaxSum(r1,j1) } D(r,j) 题目解答
#include iostream
#include algorithm
#define MAX 101
using namespace std;
int D[MAX][MAX];
int n;
int MaxSum(int i, int j){if(in)return D[i][j]; int x MaxSum(i1,j); int y MaxSum(i1,j1); return max(x,y)D[i][j];
}
int main(){int i,j;cin n;for(i1;in;i)for(j1;ji;j)cin D[i][j];cout MaxSum(1,1) endl;
}
运行该程序会超时为什么呢 原因是重复计算如果采用递规的方法深度遍历每条路径存在大量重复计算。则时间复杂度为 2n,对于 n 100 行肯定超时。
改进 如果每算出一个MaxSum(r,j)就保存起来下次用到其值的时候直接取用则可免去重复计算。那么可以用O(n2)时间完成计算。因为三角形的数字总数是 n(n1)/2
#include iostream
#include algorithm
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int MaxSum(int i, int j)
{if( maxSum[i][j] ! -1 )return maxSum[i][j]; if(in) maxSum[i][j] D[i][j]; else {int x MaxSum(i1,j); int y MaxSum(i1,j1); maxSum[i][j] max(x,y) D[i][j];}return maxSum[i][j];int main(){int i,j; cin n; for(i1;in;i)for(j1;ji;j) {cin D[i][j]; maxSum[i][j] -1;}cout MaxSum(1,1) endl;
}递归改递推
#include iostream
#include algorithm
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX]; int main(){ int i,j; cin n; for(i1;in;i) for(j1;ji;j) cin D[i][j];for( int i 1;i n; i )maxSum[n][i] D[n][i];for( int i n-1; i 1; --i ) for( int j 1; j i; j ) maxSum[i][j] max(maxSum[i1][j],maxSum[i1][j1]) D[i][j];cout maxSum[1][1] endl;
}
空间优化 没必要用二维maxSum数组存储每一个MaxSum(r,j),只要从底层一行行向上递推那么只要一维数组maxSum[100]即可,即只要存储一行的MaxSum值就可以。 进一步考虑连maxSum数组都可以不要直接用D的第n行替代maxSum即可。 节省空间时间复杂度不变
#include iostream
#include algorithm
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int * maxSum; int main(){ int i,j; cin n; for(i1;in;i) for(j1;ji;j) cin D[i][j]; maxSum D[n]; //maxSum指向第n行for( int i n-1; i 1; --i ) for( int j 1; j i; j ) maxSum[j] max(maxSum[j],maxSum[j1]) D[i][j]; cout maxSum[1] endl;
} 最长上升子序列 题目 一个数的序列bi当b1 b2 ... bS的时候我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)这里1 i1 i2 ... iK N。比如对于序列(1, 7, 3, 5, 9, 4, 8)有它的一些上升子序列如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4比如子序列(1, 3, 5, 8). 你的任务就是对于给定的序列求出最长上升子序列的长度。
输入 输入的第一行是序列的长度N (1 N 1000)。第二行给出序列中的N个整数这些整数的取值范围都在0到10000。
7
1 7 3 5 9 4 8
输出 最长上升子序列的长度。
4
解题思路 1.找子问题 “求序列的前n个元素的最长上升子序列的长度”是个子问题但这样分解子问题不具有“无后效性” 假设F(n) x,但可能有多个序列满足F(n) x。有的序列的最后一个元素比 an1小则加上an1就能形成更长上升子序列有的序列最后一个元素不比an1小……以后的事情受如何达到状态n的影响不符合“无后效性” “求以akk1, 2, 3…N为终点的最长上升子序列的长度” 一个上升子序列中最右边的那个数称为该子序列的 “终点”。 虽然这个子问题和原问题形式上并不完全一样但是只要这N个子问题都解决了那么这N个子问题的解中最大的那个就是整个问题的解。 2. 确定状态 子问题只和一个变量-- 数字的位置相关。因此序列中数的位置k 就是“状态”而状态 k 对应的“值”就是以ak做为 “终点”的最长上升子序列的长度。 状态一共有N个。 3. 找出状态转移方程 maxLen (k)表示以ak做为“终点”的最长上升子序列的长度那么 初始状态maxLen (1) 1 maxLen (k) max { maxLen (i)1i k 且 ai ak且 k≠1 } 1 若找不到这样的i,则maxLen(k) 1 maxLen(k)的值就是在ak左边“终点”数值小于ak 且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列加上ak后就能形成一个更长的上升子序列。 题目解答
#include iostream
#include cstring
#include algorithm
using namespace std;
const int MAXN 1010;
int a[MAXN];
int maxLen[MAXN];int main(){int N;cin N;for(int i 1;i N;i){cin a[i];maxLen[i] 1;}for(int i 2;i N;i){//每次求以第i个数为终点的最长上升子序列的长度for( int j 1; j i; j) //察看以第j个数为终点的最长上升子序列if( a[i] a[j] )maxLen[i] max(maxLen[i],maxLen[j]1); }cout * max_element(maxLen1,maxLen N 1 );return 0;
}} //时间复杂度O(N2) 公共子序列 题目 我们称序列Z z1, z2, ..., zk 是序列X x1, x2, ..., xm 的子序列当且仅当存在 严格上升 的序列 i1, i2, ..., ik 使得对j 1, 2, ... ,k, 有xij zj。比如Z a, b, f, c 是X a, b, c, f, b, c 的子序列。 现在给出两个序列X和Y你的任务是找到X和Y的最大公共子序列也就是说要找到一个最长的序列Z使得Z既是X的子序列也是Y的子序列。
输入 输入包括多组测试数据。每组数据包括一行给出两个长度不超过200的字符串表示两个序列。两个字符串之间由若干个空格隔开。
abcfbc abfcab
programming contest
abcd mnp
输出 对每组输入数据输出一行给出两个序列的最大公共子序列的长度。
4
2
0
解题思路 输入两个串s1,s2,设MaxLen(i,j)表示: s1的左边i个字符形成的子串与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算MaxLen(i,j) 就是本题的“状态”假定 len1 strlen(s1),len2 strlen(s2那么题目就是要求 MaxLen(len1,len2)显然MaxLen(n,0) 0 ( n 0…len1MaxLen(0,n) 0 ( n0…len2递推公式if ( s1[i-1] s2[j-1] ) //s1的最左边字符是s1[0] MaxLen(i,j) MaxLen(i-1,j-1) 1;else MaxLen(i,j) Max(MaxLen(i,j-1),MaxLen(i-1,j) );时间复杂度O(mn) m,n是两个字串长度 S1[i-1]! s2[j-1]时MaxLen(S1,S2)不会比MaxLen(S1,S2j-1) 和MaxLen(S1i-1,S2)两者之中任何一个小也不会比两者都大。 题目解答
#include iostream
#include cstring
using namespace std;
char sz1[1000];
char sz2[1000];
int maxLen[1000][1000];int main(){while( cin sz1 sz2 ){int length1 strlen(sz1);int length2 strlen(sz2);int nTmp;int i,j;for(i 0;i length1;i)maxLen[i][0] 0;for(j 0;j length2;j)maxLen[0][j] 0;for(i 1;i length1;i){for(j 1; j length2;j){if(sz1[i-1] sz2[j-1])maxLen[i][j] maxLen[i-1][j-1] 1;elsemaxLen[i][j] max(maxLen[i][j-1],maxLen[i-1][j]); }}cout maxLen[length1][length2] endl;}return 0;
}
