洛谷P2758 编辑距离

题目让我们把字符串B通过插入，删除，修改一个字符三种方式变化为字符A，求最少操作次数。此处求的是最值，考虑用动态规划

        dp [ i ] [ j ] 表示使B [ 1 ~ j ] 与 A [ 1 ~ i ]变相等要花的值,最后的答案即为dp [ lenb ] [ lena ]

        所有的动态规划题都是从已知推向未知的过程。因此我在思考一个dp时，总是从最后一个阶段着点。
对于此题，首先是边界：

        ①i==0时，即a为空，那么对应的dp[j][0]的值就为i：减少i个字符，使b转化为a

        ②j==0时，即b为空，那么对应的dp[0][i]的值就为j：增加j个字符，使b转化为a

if    当A[ i ]==B[ j ]时，如果这两位相等，意思是使 i 位与 j 位相等不需要任何代价，只需要计算使 i - 1 位与 j - 1 位相等的代价

dp[ i ][ j ]=dp[ i - 1 ] [ j - 1 ]

else

1. 删操作 : 如果删除B [ j ] 这一位，就要使B [ 1 ~ j -1 ]与A [ 1 ~ i ] 匹配. 字符串B的前j-1个字符变为字符串A的前i个需要多少步 （把字符串的第j个字符（最后一个）删除了），删除需要一步因此加1.

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

2. 插入操作 ： 插入就是删除嘛……插入一个B [ j + 1]，使B [ j + 1 ]匹配A [ i ],那么就要使B [ 1 ~ j ]与A [ 1 ~ i - 1 ] 匹配，

dp [ i ] [ j ] = dp [ i -1 ] [ j ] + 1;

3.替换操作 ： 把B[ j ]替换成能与A[ i ]匹配的数，字符串A和B的最后两个都相等了，因此都不用再考虑,字符串A的前i-1个字符变为字符串B的前j-1个需要多少步 添加需要一步因此加1,

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

将以上三种情况的最小值作为dp [ i ] [ j ] 的值

#include
using namespace std;
char a[105],b[105];
int lena,lenb,dp[105][105];
int main(){
	scanf("%sn%s",a+1,b+1);
	lena=strlen(a+1),lenb=strlen(b+1);
	for(int i=1;i<=lena;i++)dp[i][0]=i;
	for(int i=1;i<=lenb;i++)dp[0][i]=i;
    for(int i=1;i<=lena;i++){
        for(int j=1;j<=lenb;j++){
            if(a[i]==b[j])dp[i][j]=dp[i-1][j-1];
            else dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
        }
    }
    cout<