动态规划——线性DP

线性DP相对于其他DP，思路清晰，只要想好递推式以及边界问题，问题大多数迎刃而解。空说无益，先来看看一道经典例题感受一下8。

题目大概意思就是给定两个字符串，求出字符串 a[ ] 变成 b[ ] 的最小操作数。其中题目给定了三种操作方式：

（1）删除操作，比如当 a[ 1 — i - 1 ]的字符与 b[ 1 — j ] 已经匹配好了，我们看向 a[i] ,如果此时若继续 a[ 1 — i ] 与 b[ 1 — j ]匹配，则执行删除操作，即删除 a[i]

（2）添加操作，当 a[ 1 — i ]已经与 b[ 1 — j - 1 ]相匹配了，若我们看向 b[j]时，此时要想 a[i + 1] 与 b[j] 匹配，则要在 a[i + 1] 处增加与 b[j] 一样的字符。

（3）替换操作，当 a[ 1 — i - 1 ] 与 b[ 1 — j - 1 ] 相匹配，若 a[i] != b[j] ，此时就要将 a[i] 替换成 b[j]

然后便是确定集合表示方式，这里我们用 f[i][j] 表示a[i] 匹配到 b[j] 。

最后就是边界问题了，在递推式中出现 i - 1 和 j - 1 项，由于我们是从 1 — i 以及 1 — j ，因此要注意 f[0][j] 以及 f[i][0] ，这里我们根据定义进行理解，f[0][j] 表示 a[] 中没有一个字符与 b[1 — j] 匹配，因此再怎么样也要执行 j 次增加操作；同理下一个就要执行 i 次删除操作。分析完毕，最后就是源代码

#include<iostream> #include<algorithm> #include<string.h> using namespace std; const int N = 1010; int n , m; char str[N][N]; int f[N][N]; int edit_distance(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 i = 0; i <= lb ; i++ ) f[0][i] = i; 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() { scanf("%d%d" , &n , &m ); for(int i = 0 ; i < n ; i++ ) scanf("%s" , str[i] + 1 ); while(m--) { char s[N]; int limit; scanf("%s%d" , s + 1 , &limit ); int res = 0; for(int i = 0 ; i < n ; i++ ) { if(edit_distance( str[i] , s ) <= limit ) res++; } printf("%d\n" , res ); } return 0; }