Pku acm 2192 Zipper 动态规划题目解题报告(九)

时间:2022-02-23 00:34:56

http://acm.pku.edu.cn/JudgeOnline/problem?id=2192

这个题目要求判断2个字符串能否组成1个字符串,例如cattree能组成tcraete。我们定义一个布尔类型的二维数组 array,array[i][j]表示str1[i]str2[j]能否组成str[i+j].i=0或者j=0表示空字符串,所以初始化时,array[0][j]表示str1的前j个字符是否和str都匹配。

对于str=tcraete:

 

Null

c

a

t

Null

1

0

0

0

t

1

 

 

 

r

0

 

 

 

e

0

 

 

 

e

0

 

 

 

可以证明:当array[i-1][j]( array[i][j]上面一格)array[i][j-1]( array[i][j]左面一格)都为0时,array[i][j]0.array[i-1][j]( array[i][j]上面一格)1且左面字母为str[i+j]时或者当array[i][j-1]( array[i][j]左面一格)1且上面字母为str[i+j]时,array[i][j]1.这就是状态转移方程为。

核心的Java代码:

if(array[i][j-1]&&str1.charAt(j-1)==str.charAt(i+j-1)||array[i-1][j]&&str2.charAt(i-1)==str.charAt(i+j-1)) 
        

     array[i][j] = true; 
        

else 
        

     array[i][j] = false; 
        

带有详细注释的代码可以在http://download.csdn.net/user/china8848/获得