K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
序列最优变换是动态规划的典型应用场景,最小编辑距离问题是其经典代表,需通过合理的状态定义与转移推导最优解。
定义dp[i][j]表示将S的前i个元素转换为T的前j个元素的最小操作代价,若S第i个元素与T第j个元素相等,则dp[i][j] = dp[i-1][j-1]
该问题不存在最优子结构,因此无法使用动态规划方法求解
状态转移时不需要考虑删除操作对应的子状态,仅考虑插入和替换操作即可
该问题的时间复杂度最低可优化到O(m+n)