程序员人生 网站导航

动态规划总结【模板】

栏目:综合技术时间:2015-07-08 08:04:59

最长递增子序列

给定1个序列,找到最长子序列的长度,使得子序列中的所有元素被排序的顺序增加。

1.求最长递增子序列的长度O(N^2)

int Arr[30010],List[30010]; int LIS(int *Arr,int N) //arr[]寄存的是待求数组 { int Max = 0; //max为最大递增子序列的长度 for(int i = 1; i <= N; ++i) List[i] = 1; //lis[i] 寄存i之前的最大递增子序列的长度,初始都为1 for(int i = 2; i <= N; ++i) for(int j = 1; j < i; ++j) //遍历i之前所有位置 if(Arr[i] >= Arr[j] && List[i]<List[j]+1) List[i] = List[j] + 1; //arr[i]>arr[j]为递增 //lis[i]<lis[j] + 1确保为当前最长递增序列 for(int i = 1; i <= N; ++i) if(Max < List[i]) Max = List[i]; return Max; }

2.求最长递增子序列的长度O(NlogN)

int Arr[10010],List[10010]; int Stack[10010]; int LIS(int *Arr,int N) { int top = 0; Stack[top] = -1; for(int i = 1; i <= N; ++i) { if(Arr[i] > Stack[top]) Stack[++top] = Arr[i]; else { int low = 1; int high = top; while(low <= high) { int mid = (low + high)/2; if(Arr[i] > Stack[mid]) low = mid + 1; else high = mid - 1; } Stack[low] = Arr[i]; } } return top; }

最长公共子序列

给定两个序列,找出在两个序列中同时出现的最长子序列的长度。1个子序列是出现在相对顺序的序列,但不1定是连续的。

1.求最长公共子序列长度

char s1[220],s2[220]; int dp[220][220]; //求串s1和串s2的公共子序列 int lcs(char *s1,char *s2) { int len1 = strlen(s1); int len2 = strlen(s2); for(int i = 0; i <= len1; ++i) { for(int j = 0; j <= len2; ++j) { if(i == 0 || j == 0) dp[i][j] = 0; else if(s1[i-1] == s2[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[len1][len2]; }

2.求最长公共子序列长度,并输前途径

int dp[110][110],pre[110][110],len1,len2; char s1[110],s2[110]; void LCS(char *s1,char *s2) { for(int i = 0; i <= len1; ++i) pre[i][0] = 1; for(int i = 0; i <= len2; ++i) pre[0][i] = 2; //得到最长公共子序列,并标记dp[i][j]的上1个状态,用来回溯寻觅路径 for(int i = 0; i <= len1; ++i) { for(int j = 0; j <= len2; ++j) { if(i == 0 || j == 0) dp[i][j] = 0; if(s1[i-1] == s2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; pre[i][j] = 0; } else if(dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; pre[i][j] = 1; } else { dp[i][j] = dp[i][j-1]; pre[i][j] = 2; } } } } void Print(int i,int j) //回溯输出新的字符串序列 { if(i == 0 && j == 0) return ; if(pre[i][j] == 0) { Print(i-1,j-1); printf("%c",s1[i-1]); } else if(pre[i][j] == 1) { Print(i-1,j); printf("%c",s1[i-1]); } else { Print(i,j-1); printf("%c",s2[j-1]); } } void solve(char *s1,char *s2) { len1 = strlen(s1); len2 = strlen(s2); LCS(s1,s2); Print(len1,len2); printf(" "); }

最长回文子序列

给1个字符串,找出它的最长的回文子序列LPS的长度。例如,如果给定的序列是“BBABCBCAB”,则输出应当是7,“BABCBAB”是在它的最长回文子序列。

char s[2020]; int dp[2020][2020]; //dp[i][j]表示s[i~j]最长回文子序列 int LPS(char *s) { memset(dp,0,sizeof(dp)); int len = strlen(s); for(int i = len⑴; i >= 0; --i) { dp[i][i] = 1; for(int j = i+1; j < len; ++j) { if(s[i] == s[j]) //头尾相同,最长回文子序列为去头尾的部份LPS加上头和尾 dp[i][j] = dp[i+1][j⑴] + 2; else //头尾不同,最长回文子序列是去头部份的LPS和去尾部份LPS较长的 dp[i][j] = max(dp[i][j⑴],dp[i+1][j]); } } return dp[0][len⑴]; }

最小编辑距离

给定1个长度为m和n的两个字符串,设有以下几种操作:替换(R),插入(I)和删除(D)且都是相同的操作。寻觅到转换1个字符串插入到另外一个需要修改的最小(操作)数量。

int dp[1010][1010],len1,len2; char s1[1010],s2[1010]; int EditDist(char *s1,char *s2) { int len1 = strlen(s1); int len2 = strlen(s2); //当两个字符串的大小为0,其操作距离为0。 //当其中1个字符串的长度是零,需要的操作距离就是另外一个字符串的长度. for(int i = 0; i <= len1; ++i) dp[i][0] = i; for(int i = 0; i <= len2; ++i) dp[0][i] = i; for(int i = 1; i <= len1; ++i) { for(int j = 1; j <= len2; ++j) { if(s1[i-1] == s2[j-1]) //对齐s1[i⑴]和s2[j⑴],不需改变 dp[i][j] = dp[i-1][j-1]; else dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1])) + 1; //s1前缀右对齐,s2前缀右为' ',删除s1第i个字符 -> dp[i⑴][j] //s2前缀右对齐,s1前缀右为' ',删除s2第j个字符 -> dp[i][j⑴] //s1前缀右对齐,s2前缀右对齐,i、j不1样,替换 -> dp[i⑴][j⑴] } } return dp[len1][len2]; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐