acwing算法基础之动态规划--DP习题课1

这篇具有很好参考价值的文章主要介绍了acwing算法基础之动态规划--DP习题课1。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1 基础知识

暂无。。。

2 模板

暂无。。。

3 工程化

题目1：最长严格上升子序列，要求时间复杂度为 $O (n l o g n)$ 。

解题思路：保存每个长度下的最小的结尾元素值，遍历数组元素时，通过二分找到它，然后更新它即可，返回len。

该算法的关键步骤如下：

定义向量vec，vec[i]表示所有长度为i+1的上升子序列的集合，该集合当中最后一个元素最小的那个值。很显然可以知道，vec中的元素满足严格单调递增（根据vec[i]的定义即可得到）。
遍历原先的数组中的每一个元素x，在vec中找到>=x的第一个元素的下标idx：如果这个下标不存在，往vec中插入元素x；否则vec[idx] = x。

C++代码如下，文章来源地址https://www.toymoban.com/news/detail-772255.html

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];

int main() {
    
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        //在vec中找到>=a[i]的第一个元素的下标
        int idx = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
        if (idx == vec.size()) {//表示没有找到
            vec.emplace_back(a[i]);
        } else {
            vec[idx] = a[i];
        }
    }
    
    cout << vec.size() << endl;
    
    return 0;
}

题目1扩展1：求最长严格下降子序列。要求算法时间复杂度为 $O (n l o g n)$ 。

解题思路：将原先数组reverse一遍，等价于题目1。

题目2：最小编辑距离。有三种操作，插入、删除和替换，求将字符串a变成字符串b的最小操作次数。

解题思路：DP，考虑最后一次操作次数。

状态定义，f[i][j]：将字符串a的前i位变为字符串b的前j位的最小操作次数。

状态转移，有

最后一次操作是插入操作，则说明操作前已经匹配了字符串b的前j-1位，故f[i][j - 1] + 1。
最后一次操作是删除操作，则说明操作前字符串a的前i-1位已经匹配了字符串b的前j位，故f[i - 1][j] + 1。
最后一次操作是替换操作，则说明操作前字符串a的前i-1位已经匹配了字符串b的前j-1位，但可能a[i] == b[j]，则f[i - 1][j - 1]；否则f[i - 1][j - 1] + 1。

初始化，f[i][0]表示将a的前i位变成b的前0位，则值为i。f[0][j]表示将a的前0位变成b的前j位，则值为j。

最终答案，f[n][m]。

C++代码为，

#include <iostream>

using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

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

题目3：编辑距离。

思路：就是将题目2的实现套用过来，调用多次即可。

C++代码如下，

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010, M = 20;
int n, m;
char str[N][M];
int f[M][M];

int get_dis(char a[], char b[]) {
    int la = strlen(a + 1), lb = strlen(b + 1);
    
    for (int i = 0; i <= la; ++i) f[i][0] = i;
    for (int j = 0; j <= lb; ++j) f[0][j] = j;
    
    for (int i = 1; i <= la; ++i) {
        for (int j = 1; j <= lb; ++j) {
            f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);
            f[i][j] = min(f[i][j], f[i-1][j-1] + (a[i] != b[j]));
        }
    }
    return f[la][lb];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> str[i] + 1;
    
    for (int j = 1; j <= m; ++j) {
        int limit;
        char b[20];
        cin >> b + 1 >> limit;
        
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (get_dis(str[i], b) <= limit) res += 1;
        }
        cout << res << endl;
    }
    
    return 0;
}

题目4：整数划分问题。给定整数 $n$ ，求有多少种划分方案。比如3有1+1+1、1+2和3这3种划分方案。

思路：它属于计数类DP。

（解法一）

状态定义，f[i][j]：从前i个数中选，总和为j的方案数。

考虑最后一次选法，状态转移，有，

不选第i个数，即f[i-1][j]。
选1个第i个数，即f[i-1][j-i]。
选2个第i个数，即f[i-1][j - 2 * i]
……
选s个第i个数，即f[i-1][j - s * i]。

故，综合上述，f[i][j]状态转移为，

f[i][j] = f[i-1][j] + 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][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]的状态转移可以写成，

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

初始化，f[0][0] = 1。

同时利用滚动数组优化，可以有如下C++代码，

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

（解法二）
状态表示f[i][j]：总和是i，有j个数，的所有方案数。

f[i][j]的状态转移，有，

拆分出来的数的最小值是1，即·f[i-1][j-1]。
拆分出来的数的最小值大于1，即f[i-j][j]。

f[i][j]的状态转移为，

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

初始化，f[0][0] = 1。

最终答案，f[n][1] + f[n][2] + ... + f[n][n]。

C++代码如下，

#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 j = 1; j <= n; ++j) res = (res + f[n][j]) % mod;
    
    cout << res << endl;
    
    return 0;
}