华科不平凡

题解

/ 注册

全部文章 / 题解（共2篇）

判断字符串能否由另外两个字符串相交构成来自专栏

"求是否存在"，毫无疑问，又是一道动态规划题。设当前子序列为S1[0..i],S2[0..j],S3[0..i+j+1]，dp[i+1][j+1]==true表示S3[0..i+j]可以由S1[0..i]和S2[0..j]交叉组成，得到如下状态推导公式：如果S1[i]==S3[i+j+1]&am...

子序列动态规划

2020-08-25

1 1139

不同子序列个数来自专栏

“求子序列个数”，毋庸置疑，这是一道动态规划题。首先定义dp[i][j]的含义：S[0..j-1]中包含T[0..i-1]的子序列个数，接下来定义状态公式：状况1: dp[i][j]=dp[i][j-1]（如果T[i-1]!=S[j-1]）状况2：dp[i][j]=dp[i][j-1] + d...

子序列动态规划

2020-08-25

2 1149