算法题（第七届ITAT复赛试题 求算法思想）
答案:1 悬赏:60 手机版
解决时间 2021-04-27 17:09
- 提问者网友：最美的风景
- 2021-04-27 05:22
算法题（第七届ITAT复赛试题 求算法思想）
最佳答案
- 五星知识达人网友：煞尾
- 2021-04-27 06:29
编辑距离是典型的利用动态规划求解的问题，如果你不会的话最好先把这方面的基础知识学一下
思路很容易，用一个二维数组M保存子串的编辑距离，比如M(i,j)表示A(1:i)和B(1:j)的编辑距离，然后根据允许的操作来对M建立递推关系就行了追问貌似交换相邻字符不满足无后效性吧？追答对于交换相邻字符的运算，M(i,j)的递推关系中不仅有M(i-1,j)和M(i,j-1)，还含有M(i-2,j-2)，但不会影响到更远的范围，所以即使不满足无后效性也依然是简单的短递推追问能把地推方程写出来吗？谢谢!
思路很容易，用一个二维数组M保存子串的编辑距离，比如M(i,j)表示A(1:i)和B(1:j)的编辑距离，然后根据允许的操作来对M建立递推关系就行了追问貌似交换相邻字符不满足无后效性吧？追答对于交换相邻字符的运算，M(i,j)的递推关系中不仅有M(i-1,j)和M(i,j-1)，还含有M(i-2,j-2)，但不会影响到更远的范围，所以即使不满足无后效性也依然是简单的短递推追问能把地推方程写出来吗？谢谢!
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯