動态規劃（子序列（連續，非連續）問題）

最長上升子序列

#include <iostream>
#include <algorithm>
using namespace std;
int a[100005];
int dp[100005];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j < i; j ++) {
			if(a[i] >= a[j]) { //單調不減子序列 
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	cout << dp[n]; 
	return 0;
}
           

連續子序列和最大

#include <iostream>
#include <algorithm>
using namespace std;

int a[1000005];
int dp[1000005];
int maxx = -1;
int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i ++) {
		cin >> a[i];
	}
	dp[0] = a[0];
	for (int i = 0; i < n; i ++) {
		dp[i] = max(dp[i - 1] + a[i], a[i]);//用dp[i - 1] + a[i] 和 a[i]比較大小
		maxx = max(maxx, dp[i]);
	}
	cout << maxx;
}
           

最大公共子序列

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int dp[1005][1005];
int main() {
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);
	for (int i = 1; i <= str1.length(); i ++) {
		for (int j = 1; j <= str2.length(); j ++) {
			if(str1[i] != str2[j]) {
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			} else {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
		}
	}
	cout << dp[str1.length()][str2.length()];
}
           

最大公共連續子序列

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int ans = -1;
int dp[1005][1005];
int main() {
	string str1, str2;
	getline(cin, str1);
	getline(cin, str2);
	for (int i = 1; i <= str1.length(); i ++) {
		for (int j = 1; i <= str2.length(); j ++) {
			if(str1[i] != str2[i]) {
				dp[i][j] = 0;//同上一個問題的差別在這裡不相等就設定為0
			} else {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			ans = max(ans, dp[i][j]);
		}
	}
	cout << ans;
}
           

最長公共子序列

這個部落客寫的不錯

#include <iostream>
using namespace std;
int a[1005];
int b[1005];
int dp[1005][1005];

//d[i][j]表示目前a中前i個和b中前j個構成的最長公共 子序列 
int main() {
	int n, m, maxx;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= m; i ++) {
		cin >> b[i];
	}
	for (int i = 1; i <= n; i ++) {
		maxx = 0;
		for (int j = 1; j <= m; j ++) {
			dp[i][j] = dp[i - 1][j];
			if(a[i] > b[j] && maxx < dp[i - 1][j]) {
				maxx = dp[i - 1][j];
			} else if(a[i] == b[j]) {
				dp[i][j] = maxx + 1;
			}
		}
	}
	maxx = 0;
	for (int i = 1; i <= m; i ++) {
		if(dp[n][i] > maxx) {
			maxx = dp[n][i];
		}
	}
	cout << maxx << endl;
	
	return 0;
}