动态规划

用空间代替重复计算

例题

描述

对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：

1. 修改一个字符（如把“a”替换为“b”）
2. 删除一个字符（如把“traveling”变为“travelng”）

比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个字符串，写出一个算法来计算出他们的距离。

输入

第一行有一个整数n。表示测试数据的组数，
接下来共n行，每行两个字符串，用空格隔开。表示要计算距离的两个字符串
字符串长度不超过1000。

输出

针对每一组测试数据输出一个整数，值为两个字符串的距离。

样例输入

3
abcdefg  abcdef
ab ab
mnklj jlknm

样例输出

1
0
4

动态规划的解决方案通常使用一个二维数组 dp，其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符之间的编辑距离。动态规划的递推关系如下：

• 如果 s1[i-1] 等于 s2[j-1]，则 dp[i][j] = dp[i-1][j-1]，因为不需要任何操作。
• 如果 s1[i-1] 不等于 s2[j-1]，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，分别对应删除、插入和替换操作。

初始化时，dp[0][j] 是将空字符串转换为 s2 的前 j 个字符所需的操作数，即 j（全部插入）。同理，dp[i][0] 是将空字符串转换为 s1 的前 i 个字符所需的操作数，即 i（全部删除）。

最后，dp[m][n]（其中 m 和 n 分别是两个字符串的长度）就是两个字符串之间的编辑距离。

代码实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int editDistance(const string& a, const string& b) {
    int m = a.length();
    int n = b.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1});
            }
        }
    }

    return dp[m][n];
}

void solve() {
    int n;
    cin >> n;
    while (n--) {
        string a, b;
        cin >> a >> b;
        cout << editDistance(a, b) << endl;
    }
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

空间压缩后的dp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int editDistance(const string& a, const string& b) {
    int m = a.length();
    int n = b.length();
    vector<int> dp(n + 1), prev(n + 1);

    for (int j = 0; j <= n; ++j) {
        prev[j] = j;
    }

    for (int i = 1; i <= m; ++i) {
        dp[0] = i;
        for (int j = 1; j <= n; ++j) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[j] = min(prev[j] + 1, min(dp[j - 1] + 1, prev[j - 1] + cost));
        }
        swap(dp, prev);
    }

    return prev[n];
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a >> b;
        cout << editDistance(a, b) << endl;
    }
    return 0;
}

数的划分

题目描述

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

例如：$n=7$，$k=3$，下面三种分法被认为是相同的。

$1,1,5$;
$1,5,1$;
$5,1,1$.

问有多少种不同的分法。

输入格式

$n,k$ （$6<n \le 200$，$2 \le k \le 6$）

输出格式

$1$ 个整数，即不同的分法。

样例输入

7 3

样例输出

4

提示

四种分法为：
$1,1,5$;
$1,2,4$;
$1,3,3$;
$2,2,3$.

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,k,f[201][7];
int main(){
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
		f[i][1]=1;f[i][0]=1;
	}
	for (int x=2;x<=k;x++) {
		f[1][x]=0;f[0][x]=0;
	}
    for (int i=2;i<=n;i++){
		for (int x=2;x<=k;x++)
            if (i>x) {
				f[i][x]=f[i-1][x-1]+f[i-x][x];
			}
            else {
				f[i][x]=f[i-1][x-1];
			}
	}
    cout<<f[n][k];
    return 0;
}