经典动态规划

线性DP

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
37
#include <bits/stdc++.h>
using namespace std;

const int maxn = 10005;

int tr[maxn][maxn],dp[maxn][maxn];

// 利用记忆化搜索 每次如果有数值 就返回 如果没有数值就递归寻找
int dfs(int x,int y){
    if(dp[x][y]!=-1e9) return dp[x][y];
    dp[x][y] = max( dfs(x+1,y), dfs(x+1,y+1) ) + tr[x][y];
    return dp[x][y];
}

int main(){

    int n;cin >> n;
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=i;j++){
            cin >> tr[i][j];
            if(i==n) dp[i][j] = tr[i][j]; //如果是最后一层 就等于本身的数值
            else dp[i][j] = -1e9;
        }
    }
    // 其实这题这样写就比较方便了 如果转移成动态规划 就需要从下向上进行遍历
    for(int i = n-1;i>=1;i--){
        for(int j = 1;j<=i;j++){
            dp[i][j] = max(dp[i+1][j],dp[i+1][j+1]) + tr[i][j];
        }
    }
    cout << dp[1][1];
    // cout << dfs(1,1);
    return 0;
}


2.最长不下降子序列 (LIS Longest Increasing Sequence)

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
#include<bits/stdc++.h>
using namespace std;
/*
给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
可以设置dp[i] 表示的含义为以i结尾的最长的长度
然后每次遍历到这个字符 向前遍历寻找能接上的最大值
*/
int main(){
    int N;cin >> N;
    vector<int>vi;
    int dp[1006];
    int ans = -1;
    for(int i = 0;i<N;i++){
        int t;cin >> t;
        vi.push_back(t);
    }
    
    // 遍历N个数字 
    for(int i = 0;i<N;i++){
        dp[i] = 1;// 代表最小情况 为1
        for(int j = 0;j<i;j++){ //寻找接盘侠
            if(vi[j]<vi[i]){
                // 前面的比后面小 可以接盘
                dp[i] = max(dp[i],dp[j] + 1);// 就算是接盘也选最大的
            }
        }
        ans = max(ans,dp[i]);// 因为不知道是以哪个结尾可以达到最大 因此取最大值
    }
    
    cout << ans;
}

3.最长公共子序列问题 LCS

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
#include<bits/stdc++.h>
using namespace std;
/*
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少
需要开一个二维数组代表
dp[i][j] 是第一个字符串以i结尾和第二个字符串以j结尾的最长序列
而他们转移的结果是什么呢
如果这两个字符是相等的 那就会在原始的基础上增加一个长度
如果不相等 就得考虑是否还需要这个元素 也就是在dp[i-1][j] dp[i][j-1]中寻找一个最大值

*/
int dp[1006][1006];
int main(){
    int n,m;
    cin >> n >> m;
    string a,b;
    cin >> a >> b;
    a = "0"+a;
    b = "0"+b;//使得首字母下标不是0

    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            if(a[i]==b[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;
}

4.编辑距离问题 通过删除 添加 替换三种操作 将两个字符串变成完全一样的

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
#include<bits/stdc++.h>
using namespace std;
/*
有三种操作，所以有三个子集
ok子集划分完了
考虑状态转移的时候
先考虑如果我没有进行这个操作应该是什么状态
然后考虑你进行这一步操作之后会对你下一个状态造成什么影响
然后再加上之前状态表示中你决策出来的那个DP属性
这样就可以自然而然地搞出来转移方程啦

1)删除操作：把a[i]删掉之后a[1~i]和b[1~j]匹配
            所以之前要先做到a[1~(i-1)]和b[1~j]匹配
            f[i-1][j] + 1
2)插入操作：插入之后a[i]与b[j]完全匹配，所以插入的就是b[j] 
            那填之前a[1~i]和b[1~(j-1)]匹配
            f[i][j-1] + 1 
3)替换操作：把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配 
            那么修改这一位之前，a[1~(i-1)]应该与b[1~(j-1)]匹配
            f[i-1][j-1] + 1
            但是如果本来a[i]与b[j]这一位上就相等，那么不用改，即
            f[i-1][j-1] + 0

如果相等的话 就只需要在前两个状态和dp[i-1][j-1]取min
好的那么f[i][j]就由以上三个可能状态转移过来，取个min
*/
int dp[1006][1006];
int main(){
    int n,m;
    string a,b;
    cin >> n >> a >> m >> b;
    a = "0" + a;
    b = "0" + b;
    for(int i = 0;i<=max(n,m);i++) 
    {
        dp[i][0] = i;
        dp[0][i] = i;//这个初始化代表的是这种情况所需要的步骤数
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + 1;// 删除和添加操作
            if(a[i]==b[j]) dp[i][j] = min(dp[i][j],dp[i-1][j-1]);//相等状态 无需更新
            else {
                dp[i][j] = min(dp[i-1][j-1]+1,dp[i][j]);
                //这三个情况分别对应着替换 删除 添加 然后都需要操作一次 因此加一
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

5.合并石子,和哈夫曼的规则相似,只不过,每次合并的只能是相邻的两队石子

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
#include<bits/stdc++.h>
using namespace std;
/*
优先队列实现的哈夫曼树 
和哈夫曼树不一样的是 这里的合并是相邻的才可合并 不可自由合并
可以用记忆化搜索加上前缀和 因为当两个区间合并时 其代价为区间内所有元素之和
因此可以遍历所有的区间 取最小值即可 这个过程用记忆化来优化
*/

const int N = 305;
int a[N],pre[N];
int dp[N][N];// 代表该区间的最小代价

// 将区间i到j合并的最小代价
int dfs(int l,int r){
    
    if(l==r) return 0;
    int v = dp[l][r];
    if(v!=-1) return v;
    v = 1e8;
    for(int k = l;k<r;k++){
       v = min(v,dfs(l,k)+dfs(k+1,r)+pre[r]-pre[l-1]);
    //   cout  << v <<" "<< l << " "<<r <<"\n";
    }
    dp[l][r] = v;
    return v;
}

int main(){
    
    int N;
    cin >> N;
    for(int i = 0;i<=N;i++){
        for(int j = 0;j<=N;j++){
            dp[i][j] = -1;
        }
    }
    
    for(int i = 1;i<=N;i++){
        cin >> a[i];
        pre[i] = pre[i-1]+a[i];
    }
    cout << dfs(1,N);
    return 0;
}

背包问题

01背包,给定N个物品,每个物品具有价值和重量,要求你在其中任选多个,在总重量不大于V的前提下,价值最大

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
#include <bits/stdc++.h>
using namespace std;
int v[1006],w[1006];//容积和价值
int dp[1006][1006];//表示容量为这么大的时候选的最大价值

/*
背包的容量是固定的 如何放一系列的物品 使得背包的价值最高 而且不超过背包容量
dp[i][j]代表在背包容量还剩余j的前提下 处理前i件物品的最大价值
如果得到了前面的最优子结构 那下面的推导就简单了
对于一个物品k的处理很显然有两种结果 
一选这个物品 假如可以取该物品 可以选择取或者不取 在里面取max即可
假如不能取 那就直接带着容量处理下一个物品即可
下面就是选或不选的状态转移 应该是向下转移 因此遍历从小到大
dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]] + w[i]);

*/

int main()
{
    int N,V;cin >> N >> V;//N件物品 V的容量
    for(int i = 1;i<=N;i++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=V;j++){
            if(j>=v[i])dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i]] + w[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[N][V];
    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
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
int v[1006],w[1006];//容积和价值
int dp[1006][1006];//表示容量为这么大的时候选的最大价值

/*
背包的容量是固定的 如何放一系列的物品 使得背包的价值最高 而且不超过背包容量
dp[i][j]代表在背包容量还剩余j的前提下 处理前i件物品的最大价值
当处理到第k件时 (其实我可以多次选择k)
因此在处理状态时 假如不能选 自然没得说 
假如可以选 就会问选几个的问题 可以是0到符合的任意个
那既然这样 其实可以把问题甩给前面的人
反正一直甩锅 肯定会有一个人不选 那时候就可以跳出循环了
就可以和前面人说 如果你不选 就去下一层 
如果你选了 那就接着在这层 因为既然选了 谁知道你要选几次
相对01背包 就更改了后面的转移条件
dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]] + w[i]);

*/

int main()
{
    int N,V;cin >> N >> V;//N件物品 V的容量
    for(int i = 1;i<=N;i++)
    {
        cin >> v[i] >> w[i];
    }
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=V;j++){
            // 就只更改了后面 假如没选 那就跑到下一层 
            //如果选了 那就继续待在这层 因为谁知道要选几次呢
            //既然确定不了次数 那就把问题扔给自己人 让他再去判断
            if(j>=v[i])dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]] + w[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }
    cout << dp[N][V];
    return 0;
}

应用:知道存钱罐的总重量和里面各类钱币的质量,就可以得到这个存钱罐里面最多最少有多少钱

多重背包I,限制了一些物品的最大数量,求在这个前提下的最大价值

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
#include <bits/stdc++.h>
using namespace std;
int v[1006],w[1006],s[1006];//容积和价值
int dp[1006][1006];//表示容量为这么大的时候选的最大价值

/*
背包的容量是固定的 如何放一系列的物品 使得背包的价值最高 而且不超过背包容量
dp[i][j]代表在背包容量还剩余j的前提下 处理前i件物品的最大价值
这题就是限制了每种物品的个数 在此前提下的最大价值
和完全背包的区别是 不能在像那样转移了 因为那样将无非确定这个具体放进去的数量
因此这题有两个思路
1.将所有的物品都展开 相当于都算作只有一件商品 这样就可以转换成01背包问题
2.直接在每次求解的时候遍历商品的个数 然后取得最大值
*/

int main()
{
    int N,V;cin >> N >> V;//N件物品 V的容量
    for(int i = 1;i<=N;i++)
    {
        cin >> v[i] >> w[i] >> s[i];
    }
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=V;j++){
            for(int k = 0;k<=s[i];k++){//遍历这个商品需要的个数
                if(j>=k*v[i]){
                    // 相当于每次和自己进行比较 就对比出来符合情况的最大值
                    dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]*k] + w[i]*k);
                }
            }
        }
    }
    cout << dp[N][V];
    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
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
int v[1006][1006],w[1006][1006],s[1006];//容积和价值
int dp[1006][1006];//表示容量为这么大的时候选的最大价值

/*
背包的容量是固定的 如何放一系列的物品 使得背包的价值最高 而且不超过背包容量
dp[i][j]代表在背包容量还剩余j的前提下 处理前i件物品的最大价值
分组背包在于每组最多只能选一个 因此在每一组中进行遍历 取得最大值即可
*/

int main()
{
    int N,V;cin >> N >> V;//N件物品 V的容量
    for(int i = 1;i<=N;i++)// 有N组
    {
        cin >> s[i];// 表示该组的数量
        for(int j = 0;j<s[i];j++){
            cin>>v[i][j] >> w[i][j];   
        }
    }
    
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=V;j++){
            
            for(int k = 0;k<=s[i];k++){//遍历本组的所有商品 最多只能选一个 因此取max即可
                if(j>=v[i][k]){
                    // 相当于每次和自己进行比较 就对比出来符合情况的最大值
                    dp[i][j] = max(dp[i][j],dp[i-1][j-v[i][k]] + w[i][k]);
                }
            }
        }
    }
    cout << dp[N][V];
    return 0;
}
专业课 > 数据结构 > 动态规划
#动态规划 #数据结构
经典动态规划
https://rain_dew.gitee.io/2024/10/31/专业课/数据结构/动态规划/经典动态规划/
Author
Wang yulu
Posted on
October 31, 2024
Licensed under