线性动态规划基础
2018-06-17 23:38:13来源:未知 阅读 ()
最大子段和:
dp[0]=a[0];
for(int i=1; i<n; i++) { if(dp[i-1]>0) dp[i]=dp[i-1]+a[i]; else dp[i]=a[i];
}
dp[i]的值是从左至右包含a[i]的最大的子段和。dp[i]中最大的即整个串的最大的子段和。
最长公共子序列:
状态转移方程:
if(i==0 || j==0) dp[i,j]=0;
else if(X[i]==Y[j]) dp[i,j]= dp[i-1,j-1]+1;
else dp[i,j]= max(dp[i-1,j], dp[i,j-1]);
#include <iostream> #include<cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX=1000; int dp[MAX][MAX]={0}; int LCS( char *X, char *Y, int m, int n ) { for (int i=1; i<=m; i++) { for (int j=1; j<=n; j++) { if (X[i-1] == Y[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]; }
最长回文串:
#include <iostream> #include <cstdio> #include <string> #include <cstring> using namespace std; //(dp)时间复杂度O(n^2),空间复杂度O(n^2) string LPS(string s) { const int len = s.size(); if(len <= 1)return s; bool dp[len][len]; memset(dp, 0, sizeof(dp)); int resLeft = 0, resRight = 0; dp[0][0] = true; for(int i = 1; i < len; i++) { dp[i][i] = true; dp[i][i-1] = true;//这个初始化容易忽略,当k=2时要用到 } for(int k = 2; k <= len; k++)//枚举子串长度 for(int i = 0; i <= len-k; i++)//枚举子串起始位置 { if(s[i] == s[i+k-1] && dp[i+1][i+k-2]) { dp[i][i+k-1] = true; if(resRight-resLeft+1 < k) { resLeft = i; resRight = i+k-1; } } } return s.substr(resLeft, resRight-resLeft+1); } //时间复杂度O(n^2),空间复杂度O(1) string LPS2(string s) { const int len = s.size(); if(len <= 1)return s; int start, maxLen = 0; for(int i = 1; i < len; i++) { //寻找以i-1,i为中点偶数长度的回文 int low = i-1, high = i; while(low >= 0 && high < len && s[low] == s[high]) { low--; high++; } if(high - low - 1 > maxLen) { maxLen = high - low -1; start = low + 1; } //寻找以i为中心的奇数长度的回文 low = i- 1; high = i + 1; while(low >= 0 && high < len && s[low] == s[high]) { low--; high++; } if(high - low - 1 > maxLen) { maxLen = high - low -1; start = low + 1; } } return s.substr(start, maxLen); }
最长递增子序列
状态转移方程(O(n^2)):
dp[0]=1;
if(i<j && a[i]<a[j]) dp[i]=dp[j]+1;
O(nlogn):
B[i]记录的是最长递增子序列长度为i的序列的最小的末尾元素的值。
例如{1,6,4,9,5,7,8,6,8,9};
则B[1]=1;
B[2]=[6];
由于4比6小,所以此时B[2]=4;此时长度为2的LIS的最小末尾元素是4;
B[3]=9;
B[3]=5;
B[4]=7;
B[5]=8;
由于6大于dp[3]小于B[4],所以此时B[4]=6;
B[5]=8;
B[6]=9;
LIS就为6,并且末尾最小的元素是9。
更改元素值是用二分,速度更快。
#include <iostream> #include <algorithm> using namespace std; const int Max=10000; int dp[Max]; // dp[j] = max(dp[i]) + 1 int LIS_DP_N2(int *a, int n) { dp[0]=1; for(int i = 1; i < n; i++) { int maxLen = 0; for(int j = 0; j < i; j++) if(a[i] > a[j]) maxLen=max(maxLen,dp[j]); dp[i] = maxLen + 1; } int maxLIS = 0; for(int i = 0; i < n; i++) { if(maxLIS < dp[i]) maxLIS = dp[i]; } return maxLIS; } int BinarySearch(int *a, int value, int n) { int low = 0; int high = n - 1; while(low <= high) { int mid = (high + low) / 2; if(a[mid] == value) return mid; else if(value<a[mid]) high = mid - 1; else low = mid + 1; } return low; } int Len[Max]; //存放的是从左至右的LIS的值 int LIS_DP_NlogN(int *a, int n) { int B[n]; int nLISLen = 1; B[0] = a[0]; Len[0]=1; for(int i = 1; i < n; i++) { if(a[i] > B[nLISLen - 1]) { B[nLISLen] = a[i]; nLISLen++; Len[i]=nLISLen; } else { int pos = BinarySearch(B, a[i], nLISLen); B[pos] = a[i]; Len[i]=pos+1; } } return nLISLen; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 如何0基础学习C/C++? 2020-06-06
- 复习C++语法--基础篇 2020-05-27
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- C++基础 学习笔记五:重载之运算符重载 2020-04-23
- C++基础 学习笔记四:重载之函数重载 2020-04-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash