最大子段和: 最長遞增子序列: 最長迴文串: ...
最大子段和:
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];
}
最長遞增子序列:
#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); }