背包

01背包

#include <bits/stdc++.h>

using namespace std;

int dp[250], n, m;;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
    	int w, c;
    	cin >> w >> c;
    	for (int j = n; j >= w; j--) {
    		dp[j] = max(dp[j], dp[j-w] + c);
		}
	}
	cout << dp[n];
    return 0;
}

完全背包

#include <bits/stdc++.h>

using namespace std;

int dp[250], n, m;;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
    	int w, c;
    	cin >> w >> c;
    	for (int j = w; j <= n; j++) {
    		dp[j] = max(dp[j], dp[j-w] + c);
		}
	}
	cout << "max=" << dp[n];
    return 0;
}

多重背包（庆功会）

#include <bits/stdc++.h>

using namespace std;

int dp[6050], w[2020], c[2020], cnt = 0;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
    	int x, y, z;
    	cin >> x >> y >> z;
    	int s = 1;
    	while (s < z) {
			w[cnt] = s * x;
			c[cnt++] = s * y;
			z -= s;
			s *= 2;
		}
		if (z != 0) {
			w[cnt] = z * x;
			c[cnt++] = z * y;
		}

	}
	for (int i = 0; i < cnt; i++) {
		for (int j = m; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j-w[i]] + c[i]);
		}
	} 
	cout << dp[m];
    return 0;
}

最长上升子序列

#include <bits/stdc++.h>

using namespace std;

int n, a[12000], dp[12000]; 

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	dp[i] = !dp[i];
	}
    for (int i = 1; i <= n; i++) {
    	cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (a[i] > a[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		ret = max(ret, dp[i]);
	}
	cout << ret;
    return 0;
}

最长公共子序列（string 字符串）

若你想实现数组最长公共子序列，那么你可以手动修改

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
char x[N], y[N];
int dp[N][N];

int main() {
    scanf("%s %s", x+1, y+1);
    int n = strlen(x+1);
    int m = strlen(y+1);
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
    		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]);
			}
		}
	}
	cout << dp[n][m];
    return 0;
}

数字三角形（USACO）

$$dp[i][j] = \max(dp[i-1][j], \space dp[i-1][j-1])\space+\space a[i][j] $$

铺地砖

$$\begin{array}{c} dp_1=1\\ dp_2=3\\ dp_i=[dp_{i-1}\mod p +(2·dp_{i-2})\mod p]\mod p \end{array} $$