编辑距离动态规划公式
时间: 2023-10-18 09:26:32 浏览: 43
编辑距离动态规划公式可以表示为以下递推关系:
如果字符串a的第i个字符等于字符串b的第j个字符,则编辑距离dp[i][j]等于dp[i-1][j-1],即不进行任何操作。
如果字符串a的第i个字符不等于字符串b的第j个字符,则编辑距离dp[i][j]等于以下三种操作的最小值:
1. 替换操作:将字符串a的第i个字符替换为字符串b的第j个字符,此时编辑距离为dp[i-1][j-1]+1。
2. 删除操作:将字符串a的第i个字符删除,此时编辑距离为dp[i-1][j]+1。
3. 插入操作:在字符串a的第i个字符后插入字符串b的第j个字符,此时编辑距离为dp[i][j-1]+1。
因此,综合以上分析,编辑距离动态规划公式可以表示为:
如果字符串a的第i个字符等于字符串b的第j个字符,则dp[i][j]=dp[i-1][j-1];
如果字符串a的第i个字符不等于字符串b的第j个字符,则dp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [动态规划---编辑距离](https://blog.csdn.net/m0_51431003/article/details/127149925)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [基于动态规划思想的编辑距离计算](https://download.csdn.net/download/weixin_38502510/13754811)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]