这是一个思路新颖的动态规划问题，一看道题的时候看起来像搜索，一时没有想出动态规划。但是只要把思路变一下，要求给定的字串最少由几个S变换而成，每个自串能合成什么。
假设我们已经知道了，给定的串S，从第i位到第j位，能够合成的单个字母的集合，用G[i,j]表示，那么我们可以定义
F[i,j](1< =i,j<=L L为S长度)表示串S从第i位到第j位能够合成的S的最小个数
状态转移方程
F[i,j]=Min
{
F[i,k]+F[k+1,j] | i<=k<=j-1,
1 | 'S' 属于 G[i,j]
}
边界条件
F[i,j]=∞
结果就是 F[1,L]
现在只需求出G[i,j]即可。我们定义H[A,B]为字母A,B能够合成的字母的集合，对于样例
SAB
SBC
SAA
ACA
BCC
CBC
有
H['A','B']={'S'}
H['B','C']={'S','C'}
H['A','A']={'S'}
H['C','A']={'A'}
H['C','C']={'B'}
然后G[i,j]依然可以用动态规划求出。
状态转移方程
G[i,j]=Union{H[A,B] | A 属于 G[i,k] 且 B 属于 G[k+1,j] 且 i<=k<=j-1}
上式表示从G[i,k]和G[k+1,j]两个集合中，我们各取一个元素A，B，代表S[i,k]变换而成的A和S[k+1,j]变换而成的B，将A,B合成G[i,j]的一个元素。
边界条件
G[i,j]=Ø (1<=i,j<=L , i!=j)
G[i,i]={S[i]}
以上的动态规划的方法是我第一次使用的，编程的时候要格外注意细节。关于集合的运算，我们可以用两个32位整型数保存每个字母的状态，用位运算的方法求是否包含每个元素，按位求或就是并集。
Read the rest of this entry »
Recent Comments