最长公共子串类型的DP是一个经典问题,尤其适用处理两个字符串之间的匹配的问题。
- 1642. 可以到达的最远建筑(优先队列)
- 1643. 第 K 条最小指令H(组合数计数)
- 1638. 统计只差一个字符的子串数目(最长公共子串DP)
- 1639. 通过给定词典构造目标字符串的方案数H(Dp)
1642. 可以到达的最远建筑(优先队列)
最开始想到的方法是贪心,寻找合适的位置用梯子。但是这样会被hack的,没有想到使用优先队列的方法。但是想到了的话还是很自然的,维护最大的N个代价即可。
1 | class Solution { |
1643. 第 K 条最小指令H(组合数计数)
是一道利用通过组合数问题比较好的练习题。也是记住组合数的模板,C[i][j]
表示$C_i^j$.
1 | class Solution { |
1638. 统计只差一个字符的子串数目(最长公共子串DP)
比较暴力的方法是$n^4$的,依次枚举长度,s串的起始位置,t串的起始位置和匹配位置。比较聪明的方法是类似经典DP问题,最长公共子串的。dp[i][j]
表示s
结尾i
,t
结尾j
的情况下,一个不同的字符的数目。类似的我们还需要维护一个完全相同的字串的个数。
1 | // dp方法,类似与字符串匹配 |
1639. 通过给定词典构造目标字符串的方案数H(Dp)
是一道典型的DP问题,但是这个DP的设计决定了复杂度。比较好的设计思路是dp[i][j
]第i位用前j个字符,转移方程dp[i][j] = dp[i-1][j-1]*maplen+dp[i][j-1]);
这样复杂度是$n^2$。也可以设计为dp[i][j]
表示target第i位用第j个字符,转移方程为 dp[i][j] =dp[i-1][k]*maplen+dp[i][j]
,需要额外枚举k,表示第i-1位使用哪一个字符,这样的复杂度是$n^3$。
1 | //dp[i][j]第i位用前j个 |