动态规划：线性dp练习

数字三角形

题目

代码

#include<bits/stdc++.h>
using namespace std;int n;
const int N=510;
int a[N][N];
int f[N][N];//从i,j走到1,1的权重和int main()
{cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)cin>>a[i][j];for(int i=1;i<=n;i++) f[n][i]=a[n][i];for(int i=n-1;i>=1;i--)for(int j=1;j<=i;j++){f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];}cout<<f[1][1]<<endl;
}

题解

• 倒序选择不需要考虑边界问题
• dp[i][j]数组定义：从i,j走到1,1的权重和
• 初始化：f[n][i]=a[n][i];最后一层的权值就是本身的值
• 选择：从三角形矩阵中选择，只有从左边下来或者右边下来的符合
• 状态转换： f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];从选择中枚举出的规律

最长上升子序列

题目

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
int a[N];
int f[N];//以i结尾的最长上升子序列的长度int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){f[i]=1;for(int j=1;j<i;j++){if(a[j]<a[i]){f[i]=max(f[i],f[j]+1);}}}int res=0;for(int i=1;i<=n;i++)res=max(res,f[i]);cout<<res<<endl;}

题解

• dp[i]数组定义：以a[i]结尾的最长子序列的长度
• 初始化，dp[i]至少包含一个数，长度就是1
• 选择，可以从前i个数中选择，满足条件就更新
• 状态转移式： f[i]=max(f[i],f[j]+1);

最长公共子序列

题目

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];//f[i][j]表示字符串a的前i个字符和字符串b的前j个字符的LCS长度int main()
{cin>>n>>m>>a+1>>b+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;else{f[i][j]=max(f[i-1][j],f[i][j-1]);}}cout<<f[n][m]<<endl;return 0;
}

题解

这一题有一点点难思考，再分子集选择的那一块，我们看一张图：

分为最后两个字母是否相同来思考

f[i][j]表示字符串a的前i个字符和字符串b的前j个字符的LCS长度

总结：动态规划算法是一种根据已知条件推导出最优解的算法，这里的最优解就是最长公共子序列长度。通常情况下，动态规划算法包括：定义状态、状态转移方程、边界条件和初始状态等几个部分。

最短编辑距离

题目

dfs暴力版本

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n, m;
char a[N], b[N];
int res = INT_MAX;void dfs(int i, int j, int cnt)
{if (i == n && j == m) // 如果A和B都匹配完了，更新最小操作次数{res = min(res, cnt);return;}if (i < n && j < m && a[i] == b[j]) // 如果A和B当前位置的字符相等，直接比较下一个位置{dfs(i + 1, j + 1, cnt);return;}if (i < n) // 删除A当前字符dfs(i + 1, j, cnt + 1);if (j < m) // 在A当前位置插入B当前字符dfs(i, j + 1, cnt + 1);if (i < n && j < m) // 将A当前字符替换为B当前字符dfs(i + 1, j + 1, cnt + 1);
}int main()
{cin >> n >> a >> m >> b;dfs(0, 0, 0);cout << res << endl;return 0;
}

• 对于字符串A和B，从左到右比较它们每个位置的字符。

• 如果两个字符相同，则直接比较下一个位置。

• 如果两个字符不同，则可以进行以下三种操作：

  a. 删除A中的当前字符，然后比较A的下一个位置和B的当前位置。

  b. 在A的当前位置插入B的当前字符，然后比较A的下一个位置和B的下一个位置。

  c. 将A的当前字符替换为B的当前字符，然后比较A的下一个位置和B的下一个位置。

• 对于每种操作，都进行一次搜索，并记录操作次数。

• 最终返回三种操作中操作次数最小的值。

参数：

1. 当前搜索的节点或位置：在本题中，i和j分别表示字符串A和B当前比较的位置，即A的前i个字符和B的前j个字符已经匹配。
2. 当前已经进行的操作次数：在本题中，cnt表示将A变为B所需的操作次数。

在DFS中，每次搜索都有两个选择：继续深入或返回上一层。在本题中，如果A和B当前位置的字符相等，则可以直接比较下一个位置，即继续深入；否则，可以进行删除、插入和替换操作，然后继续深入。如果A和B都匹配完了，则更新最小操作次数，并返回上一层。

动态规划

#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);//数据存储到数组a的第二个元素，即a[1]中。scanf("%d%s", &m, b + 1);for (int i = 0; i <= m; i ++ ) f[0][i] = i;//将a的前0个字母和b的前i个字母匹配for (int i = 0; i <= n; i ++ ) f[i][0] = 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;
}

1. 定义状态：设f[i][j]表示将a的前i个字符变为b的前j个字符所需的最少操作次数。

2. 初始化：对于任意的i和j，当b为空字符串时，f[i][0]等于将a的前i个字符全部删除所需的最少操作次数，即f[i][0]=i；当a为空字符串时，f[0][j]等于将b的前j个字符全部插入到a中所需的最少操作次数，即f[0][j]=j。

3. 状态转移：对于f[i][j]，可以分为以下三种情况：

   a. 删除a的第i个字符，即f[i][j]=f[i-1][j]+1。

   b. 在a的第i个字符后面插入b的第j个字符，即f[i][j]=f[i][j-1]+1。

   c. 将a的第i个字符替换为b的第j个字符，如果a[i]==b[j]则f[i][j]=f[i-1][j-1]，否则f[i][j]=f[i-1][j-1]+1。

   因此，f[i][j]的值为上述三种情况的最小值。

4. 返回结果：f[n][m]即为将a变为b所需的最少操作次数。

女性知识