template:动态规划

背包问题

01背包

pAhge6s.md.png

https://www.acwing.com/problem/content/2/

dp的过程可以理解为一个全局状态更新的过程， - 1，状态函数，记f[i][j]为前i个物品放入容量为j的背包的最大价值。 - 2，观察边界情况写转态转移，当前背包容量为j，考虑？第i个物品能否放入？是否放入？
若j<w[i],无法放入，则f[i][j]=f[i-1][j]
若j>=w[i],可以放入，判断要不要放入。f[i][j]=max(f[i-1][j]+f[i-1][j-v[i]]+w[i])

pAhge6s.md.png

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(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]);
            }
        }
    }
C++

时间复杂度O(mn),无法优化，空间复杂度可以优化，事实上维度i可以利用滚动数组省去。 也就是说我们每次从后往前优化f[j],确保使用的状态都是上一层的状态，防止串联情况发生。 

1
2
3
4
5
6
7
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]);
        }
    }
C++

完全背包问题

完全背包就是在一维背包的基础上取消了对物品数量的限制。这对应着状态转移方程的变化。我们应当用刚刚更新过的值取更新现在的值 pAhoG90.md.png - 1.当前背包容量j<w[i],不能放入，则f[i][j]=f[i-1][j] - 2.当前背包容量j>=w[i],能放入，但要比较代价
(1)若第i件物品不放入背包，则 f[i][j]=f[i-1][j]
(2)若第i件物品放入背包，则 f[i][j]=f[i][j-w[i]]+c[i]
在选择第i件物品的情况下(无论多少)，背包容量为j-w[i]时包含了放入放入了第i件物品的情况(因为从前往后更新的)。容量为j时还可以再放入第i件物品，所以用f[i][j-w[i]]更新f[i][j]

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j>=v[i])  f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
C++

多重背包-朴素算法

朴素的思想是把多重背包转化为01背包处理，第i种物品可以取0件，1件…s[i]件，为此取第i种物品的情况分解为取s[i]种01背包的物品，每件体积为kv[i];价值为kw[i];

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            for(int k=0;k*v[i]<=j&&k<=s[i];k++)
            {
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
            }
        }
    }
C++

多重背包-二进制优化

二进制优化基于这样一个事实，一个数n一定可以由 一系列2的k次方的数相加表示，比如我们要取出50个苹果，我们可以分成几个箱子：（1,2,4,8,16,19），则0-50之间的任意个数都可以使用且仅使用上面的数一次后相加得到。基于这一事实，在多重背包问题中我们可以把第i件物品拆分为若干件物品，转化为01背包问题。例如si=12，拆分系数为1,2,4,5，对应(v1,wi),(2vi,2wi),4(vi,4wi),(5vi,5wi). 

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<iostream>
using namespace std;
const int N = 1010;
const int M = 2010;
int v[N],w[N],s[N],vv[12*N],ww[12*N],n,m,cnt=0;
int f[M];
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++)
    {
        int k=1;
        while(k<=s[i])
        {
            cnt++;
            vv[cnt]=k*v[i];
            ww[cnt]=k*w[i];
            s[i]-=k;
            k=k*2;
        }
        if(s[i])
        {
            cnt++;
            vv[cnt]=s[i]*v[i];
            ww[cnt]=s[i]*w[i];
            
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=m;j>=vv[i];j--)
        f[j]=max(f[j],f[j-vv[i]]+ww[i]);
    }
    printf("%d",f[m]);
}
C++
时间复杂度由O(n∑si)化为O(n∑logsi) 拆s[i]的过程自己维护一个动态数组，不要用vector，因为vector下标是从0开始的。

分组背包

n组物品和一个容量为m的背包，同一组中的物品最多选一个。
更新思路和01背包其实是一样的，不过每次更新j的时候，在当前j下试探组中每一个物品即可
由于只能取一次，滚动数组优化的时候j和01背包类似，从大到小更新。

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int k=1;k<=s[i];k++)
            {
                if(j>=v[i][k])
                f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
            }
        }
    }
C++

线性dp

数字三角形

充分体现出数组开大的好处，没赋值的地方都是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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
using namespace std;
const int N = 510;
int n,f[N][N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        scanf("%d",&f[i][j]);
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
        }
    }
    printf("%d",f[1][1]);
}
````

## 最长上升子序列(LIS)-朴素算法

题目描述：

给定一个无序的整数数组，找出其中最长上升子序列(LIS)的长度。输入：[5,7,1,9,4,6,2,8,3]

输出：4

解释：最长上升子序列是[1,4,6,8]

其长度为4。

我们使用f[i]记录以a[i]结尾的LIS长度，这样可以保证最优子结构。

并使用双指针ij进行遍历，对于当下遍历的a[i],遍历所有(1<=j<i),当下的LIS一定是前面的LIS加上a[i]得到的，为此
得到代码如下
```c++
#include <iostream>
#include <algorithm>
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;
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j]) f[i]=max(f[j]+1,f[i]);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);

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

    return 0;
}
C++

时间复杂度O(n(n − 1)/2)

贪心+二分优化LIS

pA4PrcD.png

这个算法把时间复杂度优化到了O(nlogm),原因在于最大长度的维护使用了二分。具体的操作是这样的，维护一个b[len]. pA4PHBj.png

注意b不是最长上升子序列，但b的长度始终代表出现过的最长上升子序列长度。
比如我们看上图b由259到249的更新过程，LIS实际上由259变为了24，不删除9是有这样两种考虑 - 在本题数据中4代替了5,9没必要删去，让他呆在这里即可，后续如果由2,4发展出了更长的LIS，一定是踩过9向前发展的（本题6踩过了9） - 如果9后面跟的是10，怎么办？没关系，因为4只是代替了5，由2 4 9 10和2 5 9 10构成的序列长度是一样的 无论如何，b的长度可以代表出现过的最长LIS的长度。

复习一下二分模版 

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
// l==r时退出while循环
// 全都是闭区间
// else后 l总是+1，r总是-1
// mid加不加1只取决于r=mid还是l=mid,只是为了防止l=mid出现死循环，l=1 r=2 mid=1.5=1 则l=mid=1死循环
// 不需要可以判断答案在哪一个区间，看看怎么写check能够使得 r=mid或者l=mid即可


// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：比如找第一个大于等于五的数的位置
// if(a[mid]>=5) r=mid
// else l = mid+1
int bsearch_1(int l, int r)
{
    while (l < r)
    { 
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    
        else l = mid + 1;    //严格边界
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
//比如找最后一个小于等于5的数的位置， check就是 if a[mid]<=5
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;    //严格边界
    }
    return l;
}
C++

本题

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
#include<iostream>
using namespace std;
const int N = 100006;
int a[N],b[N],len=0;
int find(int x)
{

    int l=1,r=len;
    while(l<r)
    {
        int mid =l+r>>1;
        if(b[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    b[1]=a[1]; len=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i]>b[len]) b[++len]=a[i];
        else
        {
            int j =find(a[i]);
            b[j]=a[i];
        }
    }
    printf("%d",len);
}
C++

最长公共子序列

下面的图包含了更新f和记录序列的方式，利用了前驱数组p[i][j],可以通过·回溯找到最长公共子序列

pA4VcDS.md.png

下面给出求最长长度的代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<string>
using namespace std;
const int N =1010;
int f[N][N],n,m;
//f[i][j]表示用a的前i个数，b的前j个数
int main()
{
    scanf("%d%d",&n,&m);
    string a,b;
    cin>>a>>b;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
            else f[i][j]=max(f[i-1][j],f[i][j-1]);
        }
    }
    printf("%d",f[n][m]);
}
C++

最短编辑距离

pA4dSkd.md.png

pA4av0e.md.png

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
#include<iostream>
#include<string>
using namespace std;
const int N = 1010;
int f[N][N],n,m;
string a,b;
int main()
{
    cin>>n;
    cin>>a;
    cin>>m;
    cin>>b;
    for(int i=1;i<=n;i++) f[i][0]=i;
    for(int j=1;j<=m;j++) f[0][j]=j;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1];
            else
            {
                f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
            }
        }
    }
    printf("%d",f[n][m]);
}
C++

区间dp：石子划分

如何划分石子使得代价最小？

pA4wzRI.md.png

关键在于遍历的顺序和划分的理解。按照区间长度枚举，是因为dp更新较长区间的时候，必然会用到较短区间的结果，也就是状态集合的扩张。为此 - 大循环是len的枚举。
- 在给定的的len下枚举所有长为len的区间，因此中间循环是枚举左端点，从而枚举所有长为len的区间。
- 转态转移是考虑内部所有划分得到的最小值，因此枚举划分点k即可。

pA409QP.md.png

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];

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];
    memset(f,0x3f,sizeof f);
    for(int i=1;i<=n;i++) f[i][i]=0;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r = l+len-1;
            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]);
            }
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}
C++

计数类dp-整数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int n;
int mod = 1e9+7;
int main()
{
    scanf("%d",&n);
    f[0][0]=1;
    for(int i=1;i<=n;i++) f[i][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        //如果写朴素算法，一定要判断范围
        if(j>=i) f[i][j]=(f[i-1][j]+f[i][j-i])%mod;
        else f[i][j]=f[i-1][j]%mod;
    }
    printf("%d",f[n][n]%mod);
C++

树形dp

pA45ef0.md.png

pA45npV.md.png

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 <cstring>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
vector<int> adj[N];  // 使用vector表示邻接表
int happy[N];
int f[N][2];
bool has_fa[N];

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int j : adj[u])  // 遍历u的所有子节点
    {
        dfs(j);

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

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) scanf("%d", &happy[i]);

    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        adj[b].push_back(a);  // 将a添加到b的邻接表中
        has_fa[a] = true;
    }

    int root = 1;
    while (has_fa[root]) root++;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));

    return 0;
}
C++
算法
#算法竞赛
template:动态规划
http://example.com/2024/10/20/算法/动态规划模版/
作者
bradin
发布于
2024年10月20日
许可协议