K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
序列最优变换建模用于求解两个序列之间以最小代价完成转换的问题，最典型的场景是最小编辑距离问题：给定长度为m的字符串s和长度为n的字符串t，允许对s执行插入、删除、替换单个字符三种操作，每种操作的代价均为1，求将s转换为t所需的最小操作次数。
可以定义状态dp[i][j]表示将s的前i个字符转换为t的前j个字符所需的最小操作代价，这是序列最优变换问题常用的状态定义方式
若s的第i个字符（s[i-1]）与t的第j个字符（t[j-1]）相等，则dp[i][j]可直接继承dp[i-1][j-1]的结果，无需额外操作代价
替换操作对应的状态转移逻辑为dp[i][j] = dp[i-1][j-1] + 1，其中+1代表替换操作的代价
该问题不存在重叠子问题，只能用暴力递归求解，无法通过动态规划建模优化时间复杂度