01背包
f[x]表示装x重量时最大价值，f初值0；
n物品数量，m最大重量。w表示容量，v时价值
for (int i = 1; i <= n; i++)//物品
{
for(int j=m;j>=w[i];j--){//容量
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
}
完全背包
for(int i=0;i<=m;i++){//背包容量
for(int j=1;j<=n;j++){//物品数量
if(i>=w[j]){
f[i]=max(f[i],f[i-w[j]]+v[j]);
}
}
}
01背包空间优化
dp赋初值1e9 dp[x]表示x价值的物品，所需的背包容量是多少
for(int i=1;i<=n;i++){//物品数量
for(int j=100000;j>=v[i];j--){//最大价值,其中100000是指v价值的总和
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
if(dp[j]<=w[i]){
ans=max(ans,j);
}
}
}
最大最小字段和
maxx=-1e9,minn=1e9;
s[100005],dp1[100005],dp2[100005];
for(int i=1;i<=n;i++){
cin>>s[i];//
dp1[i]=dp2[i]=s[i];
}
for(int i=1;i<=n;i++)
{
dp1[i]=max(dp1[i-1]+s[i],s[i]);
dp2[i]=min(dp2[i-1]+s[i],s[i]);
maxx=max(dp1[i],maxx);
minn=min(dp2[i],minn);
}
cout<<maxx<<minn;//maxx是最大字段和，minn最小字段和。
注意这里maxx求的是包含负数的最大字段和，如果有其他要求。通过修改maxx，minn的初始值来达到目的。
例如要求最大字段和必须是非负数，可以把maxx=0；根据特殊情况来进行特殊讨论。
以下是这道题代码
最大公共子序列
string s,t;
cin>>s>>t;
for(int i=1;i<=s.size();i++)
l[i]=s[i-1];
for(int i=1;i<=t.size();i++)
r[i]=t[i-1];
for(int i=0;i<=s.size();i++){
for(int j=0;j<=t.size();j++){
if(i0||j0){
lcs[i][j]=0;
}
else
if(l[i]==r[j])
lcs[i][j]=lcs[i-1][j-1]+1;
else
lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
}
}
cout<<lcs[s.size()][t.size()];
拓扑排序+dp
include<bits/stdc++.h>
using namespace std;
define int long long
int n,m;
vector
queue
int ans=0;
int dt[100005],num[100005];//dt存储入度数，num存储最大数量，也就是状态转移方程
void bfs(){
for(int i=1;i<=n;i++){
if(dt[i]0)
{
qt.push(i);//把入度数=0存储进去
//break;
}
}
while(qt.size()!=0){
int u=qt.front();
qt.pop();
for(int i=0;i<vt[u].size();i++){
num[vt[u][i]]=max(num[vt[u][i]],num[u]+1);
dt[vt[u][i]]--;
if(dt[vt[u][i]]0)
qt.push(vt[u][i]);
}
}
}
void solve(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
dt[b]++;
vt[a].emplace_back(b);
}
bfs();
for(int i=1;i<=n;i++){
ans=max(ans,num[i]);
}
cout<<ans;
return ;
}
signed main()
{
ios::sync_with_stdio(false);
solve();
return 0;
}
二维dp
include<bits/stdc++.h>
using namespace std;
define int long long
const int mod=1e9+7;
int dp[1005][1005];//i表示行，j表示列。
void solve(){
int n,m;
cin>>n>>m;
char c[n+5][m+5];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c[i][j];
}
}
dp[1][1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) {
if (c[i][j] == '.') {
if (i - 1 >= 1 && i - 1 <= n && c[i - 1][j] != '#') {
dp[i][j] += (dp[i - 1][j]%mod);//dp[i][j]的路径数等于dp[i-1][j]+dp[i][j-1]
dp[i][j]%=mod;
}
if (j - 1 >= 1 && j - 1 <= m && c[i][j - 1] != '#')
dp[i][j] += (dp[i ][j-1]%mod);
dp[i][j]%=mod;
}
}
}
cout<<dp[n][m];
return ;
}
signed main()
{
ios::sync_with_stdio(false);
solve();
return 0;
}
经典抛硬币问题求概率dp，概率一般都是小推大
说实话我感觉有点像背包了，dp方程有两种情况，要么是正面要么是反面
include
include "algorithm"
include "cmath"
include "set"
include "map"
include "vector"
define int long long
define PII pair<int,int>
const int N=1e6;
using namespace std;
double dp[3005][3005];
void solve(){
int n;
cin>>n;
double s[n+5];
for(int i=1;i<=n;i++){
cin>>s[i];
}
dp[1][1]=s[1];
dp[1][0]=1-s[1];
for(int i=2;i<=n;i++){
for(int j=0;j<=i;j++){
if(j==0)
dp[i][j]=dp[i-1][j](1-s[i]);
else
{
dp[i][j]=dp[i-1][j-1]s[i]+dp[i-1][j](1-s[i]);//dp[i-1][j-1]s[i]表示第i枚硬币是正面,dp[i-1][[j]*(1-s[i])表示第i枚硬币是反面。
}
}
}
double ans=0;
for(int i=n/2+1;i<=n;i++) {
ans += dp[n][i];
}
printf("%.10lf",ans);
}
signed main()
{
int t=1;
while(t--){
solve();
}
}
摸石头
dp[i]中i代表石头数为i时谁是必赢的
include
include "algorithm"
include "cmath"
include "set"
include "map"
include "vector"
define int long long
define PII pair<int,int>
const int N=1e6;
using namespace std;
int dp[N];
void solve(){
int n,k;
cin>>n>>k;
int s[n+5];
for(int i=1;i<=n;i++)
cin>>s[i];
for(int i=1;i<=k;i++){//代表石头数
for(int j=1;j<=n;j++){
if(i-s[j]>=0){
if(dp[i-s[j]]0)
dp[i]=1;
}
}
}
if(dp[k]1)
cout<<"First";
else
cout<<"Second";
}
signed main()
{
int t=1;
// cin>>t;
while(t--){
solve();
}
}
状态机模型
1049. 大盗阿福
阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺，每家店中都有一些现金。
阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
输入格式
输入的第一行是一个整数 T，表示一共有 T 组数据。
接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺。
第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量。
每家店铺中的现金数量均不超过1000。
输出格式
对于每组数据，输出一行。
该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
数据范围
1≤T≤50
1≤N≤105
输入样例：
2
3
1 8 2
4
10 7 6 14
输出样例：
8
24
样例解释
对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。
include <bits/stdc++.h>
using namespace std;
define read(a) scanf("%d", &a);
const int N = 1e5 + 10, INF = 1e9;
int t, n;
int w[N], f[N][2];
int main() {
read(t);
while(t--) {
read(n);
for(int i = 1; i <= n; i++) read(w[i]);
f[0][0] = 0, f[0][1] = -INF;
for(int i = 1; i <= n; i++) {
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + w[i];
}
printf("%d\n", max(f[n][1], f[n][0]));
}
return 0;
}
状态压缩DP
1064. 小国王
在 n×n 的棋盘上放 k 个国王，国王可攻击相邻的 8 个格子，求使它们无法互相攻击的方案总数。
输入格式
共一行，包含两个整数 n 和 k。
输出格式
共一行，表示方案总数，若不能够放置则输出0。
数据范围
1≤n≤10,
0≤k≤n2
输入样例：
3 2
输出样例：
16
include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << 10, K = 110;
int n, m;
vector
int cnt[M];
vector
LL f[N][K][M];
bool check(int state) {
for (int i = 0; i < n; i++)
if ((state >> i & 1) && (state >> i + 1 & 1))
return false;
return true;
}
int count(int state) {
int res = 0;
for (int i = 0; i < n; i++) res += state >> i & 1;
return res;
}
int main() {
cin >> n >> m;
for (int i = 0; i < 1 << n; i++)
if (check(i)) {
state.push_back(i);
cnt[i] = count(i);
}
for (int i = 0; i < state.size(); i++)
for (int j = 0; j < state.size(); j++) {
int a = state[i], b = state[j];
if ((a & b) == 0 && check(a | b))
head[i].push_back(j);
}
f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i++)
for (int j = 0; j <= m; j++)
for (int a = 0; a < state.size(); a++)
for (int b : head[a]) {
int c = cnt[state[a]];
if (j >= c)
f[i][j][a] += f[i - 1][j - c][b];
}
cout << f[n + 1][m][0] << endl;
return 0;
}
区间DP
1068. 环形石子合并
将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：
选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。
输入格式
第一行包含整数 n，表示共有 n 堆石子。
第二行包含 n 个整数，分别表示每堆石子的数量。
输出格式
输出共两行：
第一行为合并得分总和最小值，
第二行为合并得分总和最大值。
数据范围
1≤n≤200
输入样例：
4
4 5 9 4
输出样例：
43
54
include <bits/stdc++.h>
using namespace std;
const int N = 410, INF = 0x3f3f3f3f;
int n;
int w[N], s[N];
int f[N][N], g[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
w[i + n] = w[i];
}
for (int i = 1; i <= n * 2; i++)
s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len++)
for (int l = 1; l + len - 1 <= n * 2; l++) {
int r = l + len - 1;
if (l == r)
f[l][r] = g[l][r] = 0;
else {
for (int k = l; k < r; k++) {
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
int minv = INF, maxv = -INF;
for (int i = 1; i <= n; i++) {
minv = min(minv, f[i][i + n - 1]);
maxv = max(maxv, g[i][i + n - 1]);
}
cout << minv << endl << maxv << endl;
return 0;
}
树形DP
1072. 树的最长路径
给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说，要找到一条路径，使得使得路径两端的点的距离最远。
注意：路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n−1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数，表示树的最长路径的长度。
数据范围
1≤n≤10000
1≤ai,bi≤n,
−105≤ci≤10^{5}
输入样例：
6
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
输出样例：
22
include <bits/stdc++.h>
using namespace std;
const int N = 10010, M = N * 2;
int n;
int h[N], e[M], w[M], ne[M], idx;
int ans;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int u, int father) {
int dist = 0;//表示从当前点往下走的最大长度
int d1 = 0, d2 = 0;
for(int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if(j == father) continue;
int d = dfs(j, u) + w[i];
dist = max(dist, d);
if(d >= d1) d2 = d1, d1 = d;
else if(d > d2) d2 = d;
}
ans = max(ans, d1 + d2);
return dist;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
dfs(1, -1);
cout << ans << endl;
return 0;
}
数位DP
1081. 度的数量
求给定区间 [X,Y] 中满足下列条件的整数个数：这个数恰好等于 K个互不相等的 B 的整数次幂之和。
例如，设 X=15,Y=20,K=2,B=2，则有且仅有下列三个数满足题意：
17=24+20
18=24+21
20=24+22
输入格式
第一行包含两个整数 X 和 Y，接下来两行包含整数 K 和 B。
输出格式
只包含一个整数，表示满足条件的数的个数。
数据范围
1≤X≤Y≤231−1,
1≤K≤20,
2≤B≤10
输入样例：
15 20
2
2
输出样例：
3
include <bits/stdc++.h>
using namespace std;
const int N = 40;
int K, B;
int f[N][N];
void init() {
for(int i = 0; i < N; i++) {
for(int j = 0; j <= i; j++)
if(!j) f[i][j] = 1;
else f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
}
}
int dp(int n) {
if(!n) return 0;
vector
while(n) {
nums.push_back(n % B);
n /= B;
}
int res = 0, last = 0;
for(int i = nums.size() - 1; i >= 0; i--) {
int x = nums[i];
if(x) {
res += f[i][K - last];
if(x > 1) {
if(K - last - 1 >= 0) res += f[i][K - last - 1];
break;
}
else {
last++;
if(last > K) break;
}
}
if(!i && last == K) res++;
}
return res;
}
int main() {
init();
int l, r;
cin >> l >> r >> K >> B;
cout << dp(r) - dp(l - 1) << endl;
}
单调队列优化DP
135. 最大子序和
输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的连续子序列，使得子序列中所有数的和最大。
注意： 子序列的长度至少是 11。
输入格式
第一行输入两个整数 n,m。
第二行输入 n 个数，代表长度为 n 的整数序列。
同一行数之间用空格隔开。
输出格式
输出一个整数，代表该序列的最大子序和。
数据范围
1≤n,m≤300000,
保证所有输入和最终结果都在 int 范围内。
输入样例：
6 4
1 -3 5 1 -2 3
输出样例：
7
include <bits/stdc++.h>
using namespace std;
const int N = 300010, INF = 1e9;
int n, m;
int s[N];
int q[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &s[i]), s[i] += s[i - 1];
int res = -INF;
int hh = 0, tt = 0;
for (int i = 1; i <= n; i++) {
if (q[hh] < i - m) hh++;
res = max(res, s[i] - s[q[hh]]);
while (hh <= tt && s[q[tt]] >= s[i]) tt--;
q[++tt] = i;
}
printf("%d\n", res);
return 0;
}