Ⅰt’s fun ⅰfun in the sunn.这是什么意思

版权声明:本文为博主原创文章未经博主允许不得转载。 /sinat_/article/details/

判断字符串s中有多少个子序列和t相等一个字符串的子序列是将字符串中若干字符删除后形成的字符串

因为子序列中字符的顺序是固定的,所以不能采用滑动窗(滑动窗常用于解决只要求个数不要求顺序的问题)

另外,对于源字符串s假设其字符个數为n,对于目标字符串t假设其字符个数为m,那么若想要求字符串s中和t[0 : m-1]相等的子序列个数就需要先求和t[0 : m-2]相等的子序列个数又需要先求和t[0 : m-3]楿等的子序列个数…

所以本题可以使用动态规划求解,令dp[i][j]表示字符串s[0 : i-1]中和t[0 : j-1]相等的子序列个数最终要求解的是dp[n][m]

另外需要考虑的是,假设字苻串t为空即m为0,那么dp[i][0]都应该为1因为只需要将s中所有字符都删掉即可


迭代法最不容易理解的就是对dp设置初值,其实设置初值就是几个特殊情况dp[0][j]或者dp[i][0],弄清楚dp[i][j]表示的含义再进行设置初值比较好

我要回帖

更多关于 fun in the sun 的文章

 

随机推荐