동적 계획(하위 시퀀스(연속, 비연속) 문제)

#include 
#include 
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 
#include 
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 
#include 
#include 
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 
#include 
#include 
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 
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;
}