算法Basic-DP

背包问题

DP问题：两个方面去考虑：

一、状态表示，如两维度$f(i,j)$；集合（$f$代表什么集合）、属性（最大值、最小值、数量）。

集合：1、所有选法；2、条件 ①只从前$i$个物品中选；②总体积不超过j。

二、状态计算；

一般是对集合的划分：把集合$f(i,j)$分解为子集，对于背包问题，划分为包含第i个物品的，与不包含第i个物品的。

划分一般保持①不漏掉任何元素；②一般不重复

DP优化：一般是状态方程等价的变化。

01背包

每件物品最多只用1次

问题： https://www.acwing.com/problem/content/2/

$f(i,j) = max(f(i-1, j), f(i-1, j - v_i) + w_i)$

优化：$i$层的时候只依赖于$i-1$层，$j$层的选择永远有$ \le j$；因为更新依赖于 i - 1层，所以从j=m -->v_i做更新。

#include<iostream>

using namespace std;

const int N = 1010;

int v[N], w[N]; //体积、价值

int n, m; //n个物品，m大小的容量

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

优化版本：

#include<iostream>

using namespace std;

const int N = 1010;

int v[N], w[N]; //体积、价值

int n, m; //n个物品，m大小的容量

// 优化版本
int f[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++)
        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;
}

完全背包

每件物品有无限个

集合：所有只考虑前i个物品，且总体积不大于j的所有选法；

属性：max

状态计算：集合的划分：按照第i个物品选多少个（k个）进行划分；

第i物品取k个：取前i-1个物品但不含第i个物品，同时去掉k个物品i，再加回来k个物品i；

$f(i, j) = f(i-1, j - k v_i) + k w_i$

优化：

$f(i,j)=max(f(i-1, j), f(i-1, j - v) + w, f(i-1, j - 2v) + 2w,…，f(i-1, j - kv) + kw)$

$f(i, j - v) = max(f(i-1, j - v), f(i-1, j- 2v) + w, )$

相差一个$w$，所以可以用第二个式子取代第一个式子，那么便可以约掉k，得到：

$f(i,j)=max(f(i-1, j), f(i, j - v) + w)$

对比01背包$f(i,j)=max(f(i-1, j), f(i-1, j - v) + w)$，就是$i$的转移层数。

#include <iostream>
using namespace std;

const int N = 1010;

int f[N][N];

int v[N], w[N]; //物品的体积和价值。

int n, m; //物品种数和背包容积


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

优化版本：

#include <iostream>
using namespace std;

const int N = 1010;

int f[N][N];

int v[N], w[N]; //物品的体积和价值。

int n, m; //物品种数和背包容积


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

优化版本2:

#include <iostream>
using namespace std;

const int N = 1010;

int f[N];

int v[N], w[N]; //物品的体积和价值。

int n, m; //物品种数和背包容积


int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i++)
        for(int j = v[i]; j <= m; j++) //都是第i层，因此后面的f[j]依赖前面的f[j]，所以先计算前面的
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            
    cout << f[m] << endl;
    return 0;
}

多重背包

每个物品有有限个

集合：所有只从前i个物品中选，并且总体积不超过j的选法。

属性：max。

状态计算：集合的划分：按照第i个物品选多少个来划分。

s个物品最多拆分为$logs$个物品。

$2^0、2^1、2^2、2^3….、2^k，c， c < 2^{k+1}$，可以凑出来$0 1234… 2^{k+1}-1$。

也就是第i个物品选$s_i$个，把第i个物品拆成$log S_i$个，原始复杂度$NVS$ 优化为 $NVlogS$

$f(i,j) = max(f(i-1, j - v[i] k) + w[i] k);k=0,1,…,s[i]$

优化为01背包：把Si个物品拆分，对拆分的进行01背包计算；时间复杂度为$O(NVlogS)$；

#include <iostream>

using namespace std;

const int N = 110;

int f[N][N];
int v[N], w[N], s[N];
int n, 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 ++)
        for(int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            for(int k = 1; k <= s[i] && k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }       
        
    cout << f[n][m] << endl;
    
    return 0;
}

优化版本：

#include <iostream>
using namespace std;

//N的取值为1000*log2000，M为2010
const int N = 12000, M = 2010;

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

int main()
{
    cin >> n >> m;
    int cnt = 0;
    int vol, val, wei;
    for(int i = 1; i <= n; i++) 
    {
        cin >> vol >> val >> wei;
        for(int k = 1; k <= wei; k <<=1)
        {
            cnt ++;
            v[cnt] = k * vol;
            w[cnt] = k * val;
            wei -= k;
        }
        if (wei > 0)
        {
            cnt ++;
            v[cnt] = wei * vol;
            w[cnt++] = wei * val;
        }
    }
    
    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组，每组里最多选一个物品。

状态表示 $f(i,j)$ ：集合：只从前$i$组物品中选，且总体积不大于$j$的所有选法；

属性：max

状态计算：即集合划分：枚举第$i$组物品选哪个或者不选；

$f(i-1, j - v[i, k]) + w[i, k]$

// $f(i-1, j - v[i, k]) + w[i, k]$
#include <iostream>
using namespace std;

const int N = 110;
int f[N];

int v[N][N], w[N][N], s[N];

int n, m;//物品组数、背包容积、物品数量
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> s[i];
        for(int j = 1; j <= s[i]; j ++)
            cin >> v[i][j] >> w[i][j];
    }
    
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; 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]);
    
    cout << f[m];
    
    return 0;
}

线性DP

数字三角形

状态表示 $f(i,j)$：① 表示的集合：是所有从起点走到$(i,j)$的路径； ②属性：路径之和的MAX
状态计算：集合划分：一类左上方、一类来自右上方的路径；左上方：$f(i-1, j - 1) + a(i, j)$；右上方：$f(i-1, j) + a(i, j)$

计算量的计算：状态数量 × 计算每一个状态需要的时间

#include <iostream>

using namespace std;

const int N = 510;
int n;
int g[N][N],a[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= i + 1; j++)
            g[i][j] = -1e9;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j ++)
            cin >> a[i][j];

    g[1][1] = a[1][1];
    for(int i = 2; i <= n; i ++)
        for(int j = 1; j <= i; j++)
            g[i][j] = max(g[i - 1][j - 1], g[i - 1][j]) + a[i][j];

    int res = -1e9;
    for(int i = 1; i <= n; i++) res = max(res, g[n][i]);

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

    return 0;
}

最长上升子序列

状态表示$f(i)$：①表示的集合：所有以第i个数结尾的数值上升子序列的集合；②属性：集合中每一个上升子序列的长度的MAX
状态计算：集合划分：首先第i个数是确定的，倒数第二个数是什么$a_j$，那该上升子序列的最大长度为f(j) + 1，因此$a_i = max(f(j) + 1),j =0 , 1, 2,…i-1$

#include <iostream>
using namespace std;

const int N = 1010;
int a[N], f[N];

int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    f[1] = 1;
    for(int i = 2; i <= n; i ++)
    {
        for(int j = i - 1; j >= 1; j--)
            if (a[i] > a[j]) 
            {
                f[i] = max(f[i],f[j]);
            }
        f[i] += 1;
    }

    int res = 0;
    for(int  i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);

    return 0;
}

首先数组a中存输入的数（原本的数），开辟一个数组f用来存结果，最终数组f的长度就是最终的答案；假如数组f现在存了数，当到了数组a的第i个位置时，首先判断a[i] > f[cnt] ？若是大于则直接将这个数添加到数组f中，即f[++cnt] = a[i];这个操作时显然的。

时间复杂度分析：$O(nlogn)$

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

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

int find(int x) //搜索大于等于x的右边界位置
{
    int l = 1, r = cnt;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(f[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}
/*
int find(int x) //搜索的是大小等于x的左边界位置
{
    int l = 1, r = cnt;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if(f[mid] < x) l = mid;
        else r = mid - 1;
    }
    return l + 1;
}
*/
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    
    f[++cnt] = a[0];
    for(int i = 1; i < n; i++) 
    {
        if (a[i] > f[cnt]) f[++ cnt] = a[i];
        else
        {
            int h = find(a[i]);
            f[h] = a[i];
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

最长公共子序列

状态表示$f(i，j)$：①表示的集合：所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母出现的公共子序列；②属性：MAX
状态计算：集合划分：根据选或者不选：$a(i)、b(j)$。共有四种情况。分为$f(i-1, j-1)、f(i-1, j -1) + 1$，同时选一个不选另一个$f(i-1, j)、f(i, j - 1)$，这两个是与前面的集合有重叠的，但是这两个集合包含了需要的解。此时可以去掉$f(i-1, j-1)$,因为前两个集合同时包含了该集合。

#include<iostream>

using namespace std;
const int N = 1010;
char A[N], B[N];

int f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> A[i];
    for(int i = 1; i <= m; i++)
        cin >> B[i];

    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;
}

最短编辑距离

状态表示：集合：所有将$a[1- i]$变成$b[1-j]$的操作方式；

状态计算：按照最后一个字符做什么操作进行划分：

①增：$f(i, j-1) + 1$ ；②删：$f(i-1,j) + 1$ ③：改：$f(i-1, j - 1) + 1$

#include <iostream>
#include <algorithm>
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 <= n; i ++) f[i][0] = i;
    for(int i = 0; i <= m; i ++) f[0][i] = 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;
}

编辑距离

给n个字符串，再给出查询字符串与长度，问不超过长度的情况下有多少个字符串可以与该查询字符串匹配。

#include <iostream>
#include <string.h>

using namespace std;

int n, m;
const int N = 1010, M = 15;

char s[N][M];
int f[M][M];

int edit_distance(char x[], char y[])
{
    int l = strlen(x +1), r = strlen(y + 1);
    for(int i = 0; i <= l; i++) f[i][0] = i;
    for(int i = 0; i <= r; i++) f[0][i] = i;
    
    for(int i = 1; i <= l; i ++)
        for(int j = 1; j <= r; j++)
        {
            f[i][j] = min(f[i - 1][j], f[i][j - 1]) + 1;
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (x[i] != y[j]));
        }
        
    return f[l][r];
}

int main()
{
    
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%s", s[i] + 1);
    
    while( m --)
    {
        char t[20];
        int limit;
        scanf("%s%d", t + 1, &limit);
        
        int res = 0;
        
        for (int i = 1; i <= n; i++)
            if(edit_distance(s[i], t) <= limit) res++;
        
        printf("%d\n", res);
    }
    
    return 0;
}

区间DP

一般区间长度从小到大来循环。

石子合并

状态表示$f(i，j)$：①表示的集合：所有将第 $i$ 堆石子到第 $j$ 堆石子合成一堆石子的合并方式；②属性：Min
状态计算：集合划分：最后一次分界线的位置来分类：$f(i, j)= min(f(i, k) + f(k + 1, j) + s[j] - s[i - 1]),k=i到j-1$

//最后对区间长度进行枚举
#include <iostream>
using namespace std;

const int N = 310;

int f[N][N], q[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> q[i];
    for(int i = 1; i <= n; i++) q[i] += q[i - 1];
    
    for(int len = 2; len <= n; len++)
        for(int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;
            f[l][r] = 1e9;
            for(int k = l; k + 1 <= r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k +1][r] + q[r] - q[l - 1]);
        }
    
    printf("%d\n", f[1][n]);
    
    return 0;
}

计数类DP

前面的都是求最值，这个求的是个数。

整数划分

解法1：完全背包的解法；

集合：所有总和是$i$，并且恰好表示成$j$个数的和的方案；那么有f(0)=1，即一个都不选，总和是0的方案数为1.

而f(1)表示一个都不选，方案数为1，则不存在为0.

#include <iostream>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];

int main()
{
    cin >> n;
    f[0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = i; j <= n; j ++)
            f[j] =  (f[j] + f[j - i]) % mod;


    cout << f[n] << endl;

    return 0;
}

解法2：集合：所有总和是$i$，并且恰好表示成$j$个数的和的方案；属性：数量；

状态计算：$f(i, j)$：可以表示的方案中的最小值是1，最小值大于1。

左边是$f(i-1, j - 1)$；右边的每一个方案都减去1，那便等价于 $f(i-j, j)$ ；

最后对全部的$f$ 求和。

#include <iostream>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];

int main()
{
    cin >> n;
    f[0][0] = 1;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= i; j++)
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod ;
    
    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
    
    cout << res <<endl;
    
    return 0;
}

数位统计DP

计数问题

分情况讨论：对于区间内的次数，考虑前缀和的思想。

实现count(n, x)：实现1到n之间总共出现x的个数。比如要求出1在每一位上出现的次数。

设n =abcdefg ，求1在第四位上出现的次数，即转换为：1<=xxx1yyy <=abcdefg

状态压缩DP

蒙德里安的梦想

等价于按照列来横着放置小方块。

$f(i,j)$:摆放第i列，i-1列伸出来横着的方格状态为j的方案数，j为一个二进制数；

i-1列转移到i列满足：(j & k) == 0,其中k是i-1列的状态；

同时每个有效的状态满足：j | k 不存在连续奇数个零，即每个格子只能用纵向的格子来填；

位运算基础：

&	\		^	<<	>>
并	或	异或	右移	左移
1&1 = 1	1\	0 =1	1^0 = 1	1<<1 = 10	10 >> 1 = 1
1&0 = 0	0\	0 = 0	1^1 = 0	11 << 1 = 110	101 >> 1 = 10

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 13, M = 1 << N;
LL f[N][M];
int n, m;
bool st[M];



int main()
{
    while(cin >> n >> m, n|m)
    {
        for(int i = 0; i < 1 << n; i++)
        {
            int cnt = 0;
            st[i] = true;
            for(int j = 0; j < n; j++)
            {
                if(i >>j & 1)
                {
                    if(cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt++;
            }
            if (cnt & 1) st[i] = false;
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i = 1; i <= m; i++)
            for(int j = 0; j < 1 << n; j++)
                for(int k = 0; k < 1 << n; k ++)
                    if((j & k) == 0 && st[j|k])
                        f[i][j] += f[i-1][k];

        cout << f[m][0] << endl;
    }

    return 0;
}

Hamilton路径

1、状态表示： dp(i, j)集合：已经走过的所有点的集合为i，移动到j。
比如i=1110011，表示点1、2、5、6、7走过了，点3、4没走过。
状态计算：划分：倒数第二个点对把f(i，j) 分类。倒数第二个点是k，那路径0-->k->j，那么走过点的集合i中去除掉点j，然后加上从k到j的权值；最后的答案应该是dp[111..11][n-1]表示0到n-1都走过了，下一个点走到n-1的最短路径。
dp[i][j] = min{dp[i][j], dp[i - (1 << j)][k] + map[k][j]}

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20, M = 1 << N;
int dp[M][N], w[N][N];
int n;

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

    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for(int i = 0; i < 1 << n; i ++)
        for(int j = 0; j < n; j++)
            if ( i >> j & 1)
                for(int k = 0; k < n; k++)
                    if((i - (1 <<j)) >> k & 1)
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);

    cout << dp[(1 << n) -1][n - 1] << endl;

    return 0;

}

树形DP

没有上司的舞会

状态表示：集合f(u,0)：所有从以u为根的子树中选择，并且不选u这个点的方案；f(u,1)：所有从以u为根的子树中选，并且选择u的方案。
属性：MAX
状态计算：比如：f(u, 0) = sum_i (max(f(s_i, 0) , f(s_i, 1)))，s为所有子树的求和；f(u, 1) = sum_i(f(s_i, 0))。

复杂度为枚举子树节点的数目，即边的数量：$O(n)$。
1
2
3
4
5
---u---
| |
| |
| |
s1 s2

#include <iostream>
#include <cstring>

using namespace std;

const int N = 6010;

int n;
int happy[N];
int f[N][2];
bool has_parent[N];

int h[N], e[N], ne[N], idx;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}

void dfs(int u) //0选择u节点，1不选u节点
{
    f[u][0] = happy[u]; 
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u][0] += f[j][1];
        f[u][1] += max(f[j][0], f[j][1]);
    }
}
int main()
{
    
    memset(h, -1, sizeof h);
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &happy[i]);
    int emp, boss;
    for(int i = 1; i <=n - 1; i++)
    {
        scanf("%d%d", &emp, &boss);
        has_parent[emp] = true;
        add(boss, emp);
    }
    
    int root = 1; //数据从1开始
    while(has_parent[root]) root++;
    
    dfs(root);
    
    printf("%d", max(f[root][0], f[root][1]));
    
    return 0;
}

记忆化搜索

滑雪

对四个方向进行dp，每个dp返回当前位置的最大值，当到达计算过的位置便直接返回里面的值，是记忆化存储的一种实现方式。

#include <iostream>
#include <cstring>

using namespace std;

int r, c;
const int N = 310;
int m[N][N];
int f[N][N];
int h[N], e[N], ne[N], idx;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}

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

int dp(int x, int y)
{
    if(f[x][y] != -1) return f[x][y];
    
    f[x][y] = 1;
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a>=0 && a < r && b >= 0 && b < c && m[x][y] > m[a][b])
            f[x][y] = max(f[x][y], dp(a, b) + 1);
    }
    return f[x][y];
}
int main()
{
    cin >> r >> c;
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            cin >> m[i][j];
    
    memset(f, -1, sizeof f);
    int res = 0;
    for(int i = 0; i < r; i++)
        for(int j = 0; j < c; j++)
            res = max(res, dp(i, j));
            
    cout << res << endl;
    
    return 0;
}