Dynamic Programming

2023-09-28 09:36:04

文章目录

前言

动态规划，DP(Dynamic Programming)，运筹学的一个分支，同时也是求解决策过程最优化问题的过程。它和贪心一样，不是具体的某一种算法，而是一种思想。

DP的学习和使用，非常地具有挑战性，会使用DP，经常可以写出令人拍案叫绝的代码。所以它也是算法竞赛，数学建模等中的一个热点问题

DP优化是对方程进行等价变换
个人博客codeslogan: dynamic programming

背包问题

Dynamic Programming

f ( i , j ) f(i,j) f(i,j)存的是集合中所有选法的属性，是一个数

Dynamic Programming

0-1背包

每个物品只能选一次，即放入/不放入背包，使利益最大化

01背包问题（状态转移方程讲解）深蓝

状态转移方程：

f [ i , j ] = m a x ( f [ i − 1 , j ] , f [ i − 1 , j − v ] + w ) f[i,j] = max(f[i-1,j],f[i-1,j-v]+w) f[i,j]=max(f[i−1,j],f[i−1,j−v]+w)

二维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main() {
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; 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]); // 表示选上
        }
    }
    cout << f[n][m] << endl;
    
    return 0;
}

一维

关于内层循环要为何要逆序遍历？

如果顺序遍历，那么数组中来自上一轮的状态，会因顺序原因被污染。导致出现需要上一轮的状态时，却已经被覆盖了的情况。

换言之，如果j是顺序递增的话,则相当于f[i][j]变得是由f[i][j-v[i]]推出来的，

而不是由原来的f[i-1][j-v[i]]推的。与我们的状态转移方程不符。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];


int main() {
    scanf("%d%d", &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;
}

AcWing.0-1背包

完全背包

物品无限量，同一个物品可以重复放入背包中

O(n^3)，朴素做法

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

using namespace std;

const int N = 1010;

int n, m; // 物品数量，背包容量
int v[N], w[N]; // 体积，价值
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 ++ ) // 物品
        for (int j = 0; j <= m; j++) // 重量
            for (int k = 0; 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;
}

O(n^2)

对k进行优化，三维降二维，状态转移方程优化推导如下：

f [ i , j ] = m a x ( f [ i − 1 , j ] , f [ i − 1 , j − v ] + w , f [ i − 1 , j − 2 v ] + 2 w , . . . ) f[i,j] = max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,...) f[i,j]=max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2v]+2w,...)

因为i-1个物品的最大值已经在上一轮循环确定了下来，所以我们只需讨论第i个物品应该选多少个

将j替换为j-v

f [ i , j − v ] = m a x ( f [ i − 1 , j − v ] , f [ i − 1 , j − 2 v ] + w , f [ i − 1 , j − 3 v ] + 2 w , . . . ) f[i,j-v] = max(f[i-1,j-v],f[i-1,j-2v]+w,f[i-1,j-3v]+2w,...) f[i,j−v]=max(f[i−1,j−v],f[i−1,j−2v]+w,f[i−1,j−3v]+2w,...)

f [ i , j − v ] + w = m a x ( f [ i − 1 , j − v ] + w , f [ i − 1 , j − 2 v ] + 2 w , f [ i − 1 , j − 3 v ] + 3 w , . . . ) f[i,j-v]+w = max(f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,...) f[i,j−v]+w=max(f[i−1,j−v]+w,f[i−1,j−2v]+2w,f[i−1,j−3v]+3w,...)

将上述式子代入原方程，进行等价替换，得到状态转移方程：

f [ i , j ] = m a x ( f [ i − 1 , j ] , f [ i , j − v ] + w ) f[i,j]=max(f[i-1,j],f[i,j-v]+w) f[i,j]=max(f[i−1,j],f[i,j−v]+w)

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

using namespace std;

const int N = 1010;

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

降维

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

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
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 = v[i]; j <= m; j++) // 从小到大循环
            f[j] = max(f[j], f[j-v[i]] + w[i]);
                
    cout << f[m] << endl;
    
    return 0;
}

同时处理输入和状态转移

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

using namespace std;

const int N = 1010;

int n, m;
int f[N];

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

多重背包

每个物品的数量不同

朴素作法

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

using namespace std;

const int N = 110;

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

二进制优化

将一个物品的个数，表示成一段从1开始的二进制数

例如，200：1、2、4、8、16、32、64、73

为什么不选128呢？因为如果加128，可以表示的数就达到了255，超出了200。到64时，表示的数范围为127，补上一个73，就能够表示从1-200之间的任何一个数

  • 同时留意使用二进制优化时，需要开辟的数组空间为物品种数xlog2(某种物品的数量，向上取整)。因为我们在把物品数量拆成二进制表示时，要考虑到要用多少个数，才能表示出物品数量，得出上述结果
#include <iostream>
#include <algorithm>

using namespace std;

// 当有1000种物品，每种物品的数量为2000，得25000
const int N = 25000; // 留意开辟空间
int f[N];
int v[N], w[N];
int n, 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;
    
    // 0-1背包
    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;
}

分组背包

每一组中选取一样物品加入背包

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

using namespace std;

const int N = 110;
int n, m;
int f[N];
int v[N][N], w[N][N], s[N];

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

线性DP

数字三角形

DP里的Hello World!

Dynamic Programming
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

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

int main() {
    cin >> 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++) // 若从1开始，结果为负无穷，由前状态转移而来
        for (int j = 1; j <= i; j++) // 从2开始才有前状态
            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]);
        
    cout << res << endl;
    
    return 0;
}

AcWing.数字三角形

最长上升子序列

到这里为止，学习动态规划的感想是：根据题目，找到其中的一个状态，分析它是由前一个状态怎么转换得来。

比方说到下图中的6这个位置上，那么要求以6结尾的最长递增子序列要通过遍历它的前六个数，判断与它们的大小关系，再加1，取最大值。而前6个数的最长又是怎么求出来的？就是根据前5个数，以此类推

Dynamic ProgrammingDynamic Programming
#include <iostream>
#include <algorithm>

using namespace std;

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

void PrintPath(int v) {
    if (pre[v] == 0) {
        printf("%d", a[v]);
        return;
    }
    PrintPath(pre[v]);
    printf(" %d", a[v]);
}

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; // 初始化，只有1个数以第i个数结尾
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                if (f[i] < f[j] + 1) {
                    f[i] = f[j] + 1;
                    pre[i] = j; // 记录前一个点的下标，用于还原路径
                }
            }
        }
    }

    int res = -1e9, t;
    for (int i = 1; i <= n; i ++ ) {
        if (f[i] > res) {
            res = f[i];
            t = i; // 记录最长路径的最后一个下标
        }
    }
    cout << res << endl;
    PrintPath(t);

    return 0;
}

AcWing.最长上升子序列

最长公共子序列

  • 状态表示 f [ i , j ] f[i,j] f[i,j]：s1的前i个字符和s2的前j个字符的最长公共子序列
  • 状态计算： s 1 [ i ] = s 2 [ j ] s_1[i] = s_2[j] s1​[i]=s2​[j] 和 s 1 [ i ] ! = s 2 [ j ] s_1[i] != s_2[j] s1​[i]!=s2​[j]

当两个字符相等时，容易理解，由 f [ i − 1 ] [ j − 1 ] + 1 f[i-1][j-1] + 1 f[i−1][j−1]+1转移而来

而当两个字符不等时，两个字符中一定有一个可以抛弃 f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] f[i-1][j], f[i][j-1] f[i−1][j],f[i][j−1]另

外一个可能存在于最长序列，也有可能不存在，取最大值避免了复杂的讨论情况

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

using namespace std;

const int N = 1010;

int n, m;
char s1[N], s2[N];
int f[N][N];

int main() {
    cin >> n >> m >> s1 + 1 >> s2 + 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 (s1[i] == s2[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
        }
    
    
    cout << f[n][m] << endl;
    
    return 0;
}

AcWing.最长公共子序列

区间DP

  • 状态表示 f [ i , j ] f[i,j] f[i,j]：从第i堆石子到第j堆石子合并所需的代价
  • 状态计算：将区间划分成 [ i , k ] [i,k] [i,k]和 [ k + 1 , j ] [k+1,j] [k+1,j]， k = i , i + 1 , . . . , j − 1 k = i, i+1, ..., j-1 k=i,i+1,...,j−1

通过枚举区间长度，找出代价的最小值

状态转移： f [ l ] [ k ] + f [ k + 1 ] [ r ] + s [ r ] − s [ l − 1 ] f[l][k] + f[k+1][r] + s[r] - s[l-1] f[l][k]+f[k+1][r]+s[r]−s[l−1]

最后一次转移加上它的代价

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 310;
int n;
int f[N][N];
int s[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];
    
    // len=1的时候无须合并，所以从2开始
    for (int len = 2; len <= n; len++)
        // 枚举所有长度为len的情况
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len -1;
            f[l][r] = 1e8;
            // 在区间范围内进行划分
            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]);
        }
    
    cout << f[1][n] << endl;
    
    return 0;
}

AcWing.石子合并

计数类DP

状态表示中属性为count的DP问题

整数划分

一个正整数n可以表示 成若干个正整数之和，形如： n = n 1 + n 2 + . . . + n k n = n_1 + n_2 + ... + n_k n=n1​+n2​+...+nk​，其中 n 1 ≥ n 2 ≥ . . . ≥ n k , k ≥ 1 n_1 \ge n_2 \ge ... \ge n_k, k \ge 1 n1​≥n2​≥...≥nk​,k≥1。

我们将这样的一种表示 称为正整数n的一种划分。

现在给定一个正整数n，请你求出n共有多少种不同的划分方法。

输入格式

共一行，包含一个整数n。

输出格式

共一行，包含一个整数，表示总划分数量。

由于答案可能 很大，输出结果请对 1 0 9 + 7 10^9+7 109+7取模。

数据范围

1 ≤ n ≤ 1000 1 \le n \le 1000 1≤n≤1000

转化为完全背包问题

  • 状态表示 f [ i , j ] f[i,j] f[i,j]：从1-i当中选，使体积恰好是j的数量
  • 状态计算：针对第i个数时，有不选、选i、选2i、……、选si这些情况，容易将其转化为完全背包问题

选几个i，就要在之前的状态中提前预留出位置，因此减去

f [ i , j ] = f [ i − 1 , j ] + f [ i − 1 , j − i ] + f [ i − 1 , j − 2 i ] + . . . + f [ i − 1 , j − s i ] f[i,j] = f[i-1,j]+f[i-1,j-i]+f[i-1,j-2i]+...+f[i-1,j-si] f[i,j]=f[i−1,j]+f[i−1,j−i]+f[i−1,j−2i]+...+f[i−1,j−si]

将j等价替换为j-i

​ f [ i , j − i ] = f [ i − 1 , j − i ] + f [ i − 1 , j − 2 i ] + f [ i − 1 , j − 3 i ] + . . . + f [ i − 1 , j − s i ] f[i,j-i] = f[i-1,j-i]+f[i-1,j-2i]+f[i-1,j-3i]+...+f[i-1,j-si] f[i,j−i]=f[i−1,j−i]+f[i−1,j−2i]+f[i−1,j−3i]+...+f[i−1,j−si]

代入原式，得

f [ i , j ] = f [ i − 1 , j ] + f [ i , j − i ] f[i,j]=f[i-1,j]+f[i,j-i] f[i,j]=f[i−1,j]+f[i,j−i]

#include <iostream>

using namespace std;

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

int main() {
    cin >> n;
    
    f[0] = 1; // 一个数都不选，总和为0时的方案
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j++)
            f[j] = (f[j] + f[j-i]) % INF;
    
    cout << f[n] << endl;
    
    return 0;
}

计数类DP

  • 状态表示 f [ i , j ] f[i,j] f[i,j]：所有数的总和为i，并且表示成j个数的和的个数
  • 状态计算：将集合划分成两种情况：j个数中最小值为1和最小值大于1
    • 最小值为1： f [ i − 1 , j − 1 ] f[i-1,j-1] f[i−1,j−1]
    • 最小值大于1： f [ i − j , j ] f[i-j,j] f[i−j,j]（每个值都减去1，一共减j，方案数不变）

状态转移方程为

f [ i , j ] = f [ i − 1 , j − 1 ] + f [ i − j , j ] f[i,j]=f[i-1,j-1]+f[i-j,j] f[i,j]=f[i−1,j−1]+f[i−j,j]

最后的结果需要对式求和 f [ n ] [ i ] , i = 1 , 2 , . . . , n f[n][i],i=1, 2,...,n f[n][i],i=1,2,...,n

#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

状态压缩DP

树形DP

记忆化搜索

参考资料

AcWing算法基础课，欢迎大家报名，强推噢！！！y总带你感受算法之美！

上一篇：12种JavaScript中最常用的数组操作整理汇总（2）


下一篇：封装了一个react下拉刷新上拉加载组件