Leetcode 115 不同的子序列

时间:2024-02-15 14:19:18

题意理解:

        给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 109 + 7 取模。

        

        即此题可以理解为:从s中删除元素去构造t,有多少种方法

        或者也可以理解为:s中按顺序取t,有多少个

        则一定有s和t的最长公共子序列为t, 那么s中有多少个这样的最长公共子序列呢。

        这里采用动态规划思路来解题,则首先要明确dp数组的含义。

解题思路:

        (1)定义dp数组

        dp[i][j]表示s的第i个元素前有多少个t的第j个元素前子串。

        (2)初始化

        dp[i][0]表示s的第i个元素前有多少个空串,dp[i][0]=1

        dp[0][j]表示空串里有多少个t的字串,dp[0][j]=0

        特别的dp[0][0]=1

        (3)递推公式

        当且仅当:        s[i-1]==t[j-1]时

                此时有两种情况:

                dp[i][j]=使用这个可以匹配的字符+不适用这个可以匹配的,尝试下一个可以匹配的字符

                          =dp[i-1][j-1](使用是s[i-1])+dp[i-1][j](不使用s[i-1],继续下一字符匹配)

        否则:      dp[i][j]=(不是使用该字符匹配)dp[i][j-1]

        (4)遍历顺序:总是从上到下,从左到右

        (5)返回

            dp[s.size][t.size]