字符串匹配动态规划
题目
思路
1. 共性: 基于最后一位是否相同来决定递归函数的走向
2. 第一题. dp[i][j] 表示 str1[0...i], str2[0...j] 之间的距离
dp[i][j] = dp[i-1][j-1] if str1[i] == str2[j]
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) else
3. 第二题. dp[i][j] 表示 str1[0...i] 能否被 str2[0...j] 和 str3[0...i-j] 表示
dp[i][j] = dp[i-1][j-1] if(str1[i] == str2[[j])
dp[i][j] = dp[i-1][j] if(str[i] == str3[i-j])
4. 第三题. 统计方案数.
dp[i][j] 表示 str1[0...i] 由 str2[0...j] 表示的方案数
dp[i][j] = dp[i-1][j-1] + dp[i][j-1] if(str1[i] == str2[j])
dp[i][j] = dp[i][j-1] else