Dp 动态规划

闫氏 Dp 分析法：
20250805213522

背包问题

0，1 背包问题

n 个物品，v 表示物品的体积，w 表示物体的价值，每个物品只能使用一次。
20250805213553
状态转移方程：dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
朴素写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];//v代表体积，w代表价值
int f[N][N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];
    for(int i=1;i<=n;i++)//i代表这n件物品
    {
        for(int j=1;j<=m;j++){//j代表背包容量
            if(v[i]>j)//如果v[i]的容量大于当前的背包容量则不装进行下一个
                f[i][j]=f[i-1][j];
            else f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);//如果v[i]的容量小于当前背包容量则可以选择装与不装得到最大值
        }
    }

    cout<<f[n][m]<<endl;//输出最后的一个一定是最大的
    return 0;
}

一维优化、滚动数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N];//v代表体积，w代表价值
int dp[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)//i代表这n件物品
    {
        cin>>v[i]>>w[i];//在线算法
        for(int j=m;j>=v[i];j--){//j代表背包容量，滚动数组必须倒序遍历
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//滚动数组
        }
    }
    cout<<dp[m]<<endl;//输出最后的一个一定是最大的
    return 0;
}

完全背包问题

n 个物品，v 表示物品的体积，w 表示物体的价值，每个物品可以使用无限次。
状态转移方程：dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
算法模版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int v[N],w[N];
int dp[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){//遍历物品
        cin>>v[i]>>w[i];//在线算法
        for(int j=v[i];j<=m;j++){//正序遍历背包容量
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//滚动数组
        }
    }
    cout<<dp[m]<<endl;//输出答案
    return 0;
}

多重背包问题 1(3 重循环写法)

dp[i][j]=max(dp[i][j],dp[i-1]j-v[i]k]+w[i]k);
n 个物品，v 表示物品的体积，w 表示物体的价值，每个物品可以使用多次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using namespace std;
int n,m;
int v[N],w[N],s[N];
int dp[N][N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++)//物品
        for(int j=0;j<=m;j++)//背包容量
            for(int k=0;k<=s[i]&&k*v[i]<=j;k++)
                dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]*k]+w[i]*k);
    cout<<dp[n][m]<<endl;
    return 0;
}

多重背包问题 2(二进制优化)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }//二进制优化操作

    n = cnt;

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}

分组背包问题

有 n 组物品，m 的体积，每组物品只能选择一个
状态转移方程：f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
using namespace std;
const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=0;i<n;i++){
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=1;k--)也可以
                if(j>=v[i][k])
                    f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<f[m]<<endl;
}

线性 DP

数字三角形

20250805213743
状态转移方程：f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using namespace std;
const int N=510,INF=1e9;
int n;
int a[N][N];
int f[N][N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            f[i][j]=-INF;
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//状态转移方程
    int res=-INF;
    for(int i=1;i<=n;i++)res=max(res,f[n][i]);
    printf("%d",res);
    return 0;
}

最长上升子序列

一般写法

状态转移方程：if(a[j]<a[i])f[i]=max(f[i],f[j]+1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
const int N = 1010;

int n;
int a[N],f[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )scanf("%d",&a[i]);
    for (int i = 1; i <= n; i ++ ){
        f[i]=1;//只有a[i]一个数
        for (int j = 1; j <= i; j ++ )
            if(a[j]<a[i])
                f[i]=max(f[i],f[j]+1);
    }
    int res=0;
    for (int i = 1; i <= n; i ++ )res=max(res,f[i]);
    printf("%d\n",res);
    return 0;
}

二分优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];//替换或添加
    }

    printf("%d\n", len);

    return 0;
}

最长公共子序列

状态转移方程：

f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin>>n>>m>>a+1>>b+1;
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

最短编辑距离

20250805213938
状态转移方程:

f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//状态转移方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    scanf("%d%s", &n, a+1);
    scanf("%d%s", &m, b+1);

    for (int i = 0; i <= m; i ++ )f[0][i]=i;
    for (int i = 0; i <= n; i ++ )f[i][0]=i;//初始化字符串的编辑操作
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j])f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//状态转移方程
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

区间 DP

石子合并

20250805214020
状态转移方程找到最小值状态转移方程为 f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
const int N = 310;

int n;
int s[N];
int f[N][N];//状态表示：集合f[l][r]为[l,r]区间；属性：所堆成的最小值
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )scanf("%d",&s[i]);
    for (int i = 1; i <= n; i ++ )s[i]+=s[i-1];//前缀和用来求一段区间的和

    for (int len = 2; len <= n; len ++ )//区间长度为len//枚举长度
        for (int i = 1; i+len-1 <= n; i ++ ){//意思就是i在区间[1,n-len+1]中去//枚举区间
            int l=i,r=i+len-1;//区间在[i,i+len-1]中间长度为len//设置l和r的区间
            f[l][r]=1e9;//初始化最大值
            for (int k = l; k < r; k ++ )//枚举分界点//不取r
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);//找到最小值状态转移方程为f[l][k]+f[k+1][r]+s[r]-s[l-1];
        }
    printf("%d\n",f[1][n]);//输出区间[1,n]的最小值
    return 0;
}

计数类 Dp

状态转移方程：f[j]=(f[j-i]+f[j])

1

数位统计 Dp

20250805214239
20250805214257

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;

//因为我们举的分类中，有需要求一串数字中某个区间的数字，例如abcdefg有一个分类需要求出efg+1
int get(vector<int> num,int l,int r){
    int res=0;
    for(int i=l;i>=r;i--)res=res*10+num[i];//这里从小到大枚举的是因为下面count的时候读入数据是从最低为读到最高位，那么此时在num里，最高位存的就是数字的最低位，那么假如我们要求efg，那就是从2算到0
    return res;
}

int power10(int i)//这里有power10是因为有一个分类需要求得十次方得值
{
    int res=1;
    while(i--)res*=10;
    return res;
}

int count(int n,int x){
    if(!n)return 0;//n=0则返回0
    vector<int> num;//num用来存储数中的每一位数字
    while(n){
        num.push_back(n%10);
        n/=10;
    }
    n=num.size();//得出它的长度
    int res=0;
    for (int i = n-1-!x; i >=0; i -- )
    //这里需要注意，我们的长度需要减一，是因为num是从0开始存储，而长度是元素的个数，因此需要减1才能读到正确的数值，而!x出现的原因是因为我们不能让前导零出现，如果此时需要我们列举的是0得出现的次数，那么我们自然不能让他们出现第一位，而是从第二位开始枚举
    {
        if(i<n-1)//其实这里可以不同if判断，因为for循环里面实际上就已经达成了if得判断，但为了方便理解还是加上if来理解，这里i要小于n-1的原因是因为我们不能越界只有7位数就最高从七位数开始读起
        {
            res+=get(num,n-1,i+1)*power10(i);//这里就是第一个分类，000~abc-1，那么此时情况个数就会是abc*103,这里的3取决于后面的efg的长度，假如他是efgh，那么就是4
            //这里的n-1,i+1,自己将数组列出然后根据分类标准就可以得出为什么l是n-1,r=i+1
            if(!x)res-=power10(i);//假如此时我们要列举的是0出现的次数，因为不能出现前导零，这样是不合法也不符合我们的分类情况，例如abcdefg我们列举d，那么他就得从001~abc-1，这样就不会直接到efg，而是会到0efg，因为前面不是前导零，自然就可以列举这个时候0出现的次数，所以要减掉1个power10
        }
        if(num[i]==x)res+=get(num,i-1,0)+1;
        else if(num[i]>x)res+=power10(i);
    }
    return res;//返回res，即出现次数
}

int main()
{
    int a,b;
    while(cin>>a>>b,a||b){
        if(a>b)swap(a,b);//a大于b则交换a，b使得变成合法参数
        for(int i=0;i<10;i++)
            cout<<count(b,i)-count(a-1,i)<<' ';//使用前缀和思想解决[a,b]的i出现的次数
        cout<<endl;
    }
    return 0;
}

状态压缩 Dp

蒙德里安的梦想

状态转移方程：

if((j&k)==0&&st[j|k])
f[i][j]+=f[i-1][k];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;

const int N = 12,M=1<<N;

int n,m;
long long f[N][M];
bool st[M];

int main()
{
    int n,m;
    while(cin>>n>>m,n||m){
        memset(f, 0, sizeof f);
        //预处理：判断合并列的状态i是否合法
        //如果合并列的某行是1表示横放，是0表示竖放
        //如果合并列不存在连续的奇数个0，即为合法状态
        for (int i = 0; i < 1<<n; i ++ ){
            st[i]=true;
            int cnt=0;//记录合并列中连续0的个数
            for (int j = 0; j < n; j ++ ){
                if(i>>j&1){//如果是1
                    if(cnt&1){//如果连续0的个数是奇数
                        st[i]=false;//记录i不合法
                        break;
                    }
                }else cnt++;//如果是0，记录0的个数
            }
            if(cnt&1)st[i]=false;//处理高位0的个数
        }
        //状态计算
        f[0][0]=1;//第0列不横放是一种合法的方案
        for (int i = 1; i <= m; i ++ )//阶段：枚举列
            for (int j = 0; j < 1<<n; j ++ )//状态：枚举i列的状态
                for (int k = 0; k < 1<<n; k ++ )//状态：枚举i-1列的状态
                    //两列状态兼容：不出现重叠的1，不出现连续奇数个0
                    if((j&k)==0&&st[j|k])
                        f[i][j]+=f[i-1][k];
        cout<<f[m][0]<<endl;//第m列不横放，既答案
    }
    return 0;
}

树形 Dp

没有上司的舞会

状态转移方程：

f[u][0]+=max(f[j][0],f[j][1]);
f[u][1]+=f[j][0];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;

const int N = 6010;

int n;
int w[N];//每个节点的高兴度
int h[N], e[N], ne[N], idx;//邻接表存储树

bool st[N];//判断是否有父节点
int f[N][2];

void add(int a, int b)  // 添加一条边a->b
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u){
    f[u][0]=0;
    f[u][1]=w[u];//初始化f[u][1]，当第二维是0则不选该点即高兴度为0，同理f[u][1]=w[u];
    for (int i = h[u]; i!=-1 ; i =ne[i] ){//遍历u的子节点进行深度优先遍历
        int j=e[i];
        dfs(j);
        //状态转移方程
        f[u][0]+=max(f[j][0],f[j][1]);//f[u][0]表示不选择父节点u，所以在f[j][0]和f[j][1]取最大值
        f[u][1]+=f[j][0];//f[u][1]表示选择根节点u，所以累加不选择子节点的f[j][0]
    }
}

int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )cin>>w[i];
    memset(h, -1, sizeof h);
    for (int i = 0; i < n-1; i ++ ){
        int a,b;
        cin>>a>>b;
        add(b,a);
        st[a]=true;//存储是否存在父节点
    }
    int root=1;
    while(st[root])root++;//判断是否是根节点
    dfs(root);//dfs对f[i][j]进行状态转移计算
    cout<<max(f[root][0],f[root][1])<<endl;//取选与不选根节点的最大值
    return 0;
}

记忆化搜索

用 dfs 来解决 dp 问题

滑雪

状态转移方程：v=max(v,dp(a,b)+1);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
using namespace std;
const int N = 310;

int n,m;
int h[N][N];
int f[N][N];

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int dp(int x,int y){
    int &v=f[x][y];
    if(v!=-1)return v;//记忆化搜索核心
    v=1;
    for (int i = 0; i < 4; i ++ ){
        int a=x+dx[i],b=y+dy[i];
        if(a>=1&&a<=n&&b>=1&&b<=m&&h[a][b]<h[x][y])//判断是否越界且上一个经过的点的高度是否大于当前高度
            v=max(v,dp(a,b)+1);
    }
    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &h[i][j]);
    memset(f, -1, sizeof f);
    int res=0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            res=max(res,dp(i,j));
    printf("%d\n",res);
    return 0;
}