【最短编辑距离】https://leetcode.cn/problems/edit-distance/description/

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

int minDistance(string word1,string word2){
    int m=word1.size();   // 单词长度
    int n=word2.size();

    word1='#'+word1;  //【占位】下标0为空串，而不是第一个字母
    word2='%'+word2;

    int dp[m+1][n+1];

    // 遍历所有子问题
    for(int i=0;i<=m;i++){
        for(int j=0;j<=n;j++){
            if(i==0) dp[i][j]=j;
            if(j==0) dp[i][j]=i;
            if(word1[i]==word2[j]) dp[i][j]=dp[i-1][j-1];  //不替换
            else dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
        }
    }
    return dp[m][n];  //得到大问题
}

int main(){
    string word1="horse", word2="coser";
    cout<<minDistance(word1,word2);
    return 0;
}

/* ERROR
// return dp[i][j];  //× 变量声明之外
// dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1;
       min()————只接受两个参数，要通过嵌套调用来比较三个值
// return 0; 别漏掉
*/