状态转移方程是什么要求：简明,通俗易懂,适于初学者还有,则么把题目转化成状态转移方程
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/24 13:38:01
状态转移方程是什么要求：简明,通俗易懂,适于初学者还有,则么把题目转化成状态转移方程
状态转移方程是什么
要求：简明,通俗易懂,适于初学者
还有,则么把题目转化成状态转移方程
状态转移方程是什么要求：简明,通俗易懂,适于初学者还有,则么把题目转化成状态转移方程
一个字符串可以插入、删除、改变到另一个字符串,求改变的最小步骤.和最长公共子序列类似,用二维数组opt[i][j]记录字符串a中的前i个字符到字符串b中的前j个字符匹配所需要的最小步数.假如已知AG到GT的最小步数,AGT到GT的最小步数,AG到GTT的最小步数,求AGT到GTT的最小步数,此时T= =T,这个值是AG到GT的最小步数,AGT到GT的最小步数加一(AGT到GT的最小步数等于AGTT到GTT的最小步数,加一是将T删除的一步),AG到GTT的最小步数加一(AG到GTT的最小步数等于AGT到GTTT的最小步数,加一是在AGT上增加T的一步).假如已知AG到GT的最小步数,AGA到GT的最小步数,AG到GTT的最小步数,求AGA到GTT的最小步数,此时A!=T,这个值是AG到GT的最小步数加一(A改变为T),AGA到GT的最小步数加一(AGA到GT的最小步数等于AGAT到GTT的最小步数,加一是将T删除的一步),AG到GTT的最小步数加一(AG到GTT的最小步数等于AGA到GTTA的最小步数,加一是在GTTA上删除A的一步).所以状态转移方程：
初始化的时候和最长公共子序列不同,因为第0行,第0列表示null转化到字符串情况,结果是字符串的长度：
if(str1.charAt(i-1)==str2.charAt(j-1))
array[i][j] = Math.min(Math.min(array[i-1][j-1],array[i-1][j]+1),array[i][j-1]+1);
else
array[i][j] = Math.min(Math.min(array[i-1][j-1]+1,array[i-1][j]+1),array[i][j-1]+1);
for(int i=0;i