本文共 1611 字，大约阅读时间需要 5 分钟。

题目描述：

2 abba addba 1 d b a dd 0

Case #1: happy Case #2: unhappy

思路：  dp[i][j] = true  代表小明的前 j 个字符可以 转换成前 小西 前 i 个字符。

             dp[i][j] 为 true 的 三种情况：

             1. 小明前 j - 1 个字符 已经可以转换成  小西 前 i 字符 ， 那么 前 j 个 肯定也行。

             2.小明 第 j 个字符 等于 小西 第 i 个 字符， 且 dp[i-1][j-1] 为 true.

             3.小明 第 j 个字符 可以以通过转换 等于 小西 第 i 个 字符

参考代码：

#include 
   
    #include 
    
     using namespace std;const int N = 1010;// 如果 judge[i][j] == true, 则 'a'+i 可转化成为 'a'+jbool judge[30][30];// 如果 dp[i][j] == true, 则代表小明的前 j 个字符可以 转换成前 小西 前 i 个字符bool dp[N][N];int main() {    int T, m;    // ch 小西的字符串， sh 小明的字符串    string ch, sh;    cin >> T;    for(int t=1; t<=T; t++) {        cin >> ch >> sh >> m;        // 字符串的下标从 1 开始        ch = "#"+ch;        sh = "#"+sh;        memset(judge, 0, sizeof(judge));        char a, b;        for(int i=1; i<=m; i++) {            cin >> a >> b;            judge[b-'a'][a-'a'] = true;        }        int chLength = ch.length();        int shLength = sh.length();        memset(dp, 0, sizeof(dp));        for(int i=0; i