题意理解
有 NNN 卷羊皮纸,每卷长度为 LLL。要从中拼出目标串 TTT,规则是:每次选取字符时,列下标必须严格递增(但可以来自任意一卷羊皮纸)。求方案数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
关键观察: 列下标必须严格递增,意味着每一列最多只能贡献 TTT 的一个字符。
使用动态规划,按列从左到右遍历。
设 dp[i]dp[i]dp[i] 表示:已经匹配了 TTT 的前 iii 个字符的方案数。
对于第 kkk 列,预处理 cnt[c]cnt[c]cnt[c] = 该列字符 ccc 在所有羊皮纸中出现的次数。
状态转移(倒序枚举,避免同一列重复使用):
dp[i]=dp[i]+dp[i−1]×cnt[T[i−1]]dp[i] = dp[i] + dp[i-1] \times cnt[T[i-1]] dp[i]=dp[i]+dp[i−1]×cnt[T[i−1]]
边界条件:
* dp[0]=1dp[0] = 1dp[0]=1:还没匹配任何字符,方案数为 1
答案: dp[∣T∣]dp[|T|]dp[∣T∣]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码