lintcode118. 不同的子序列动态规划

深藏阁楼爱情的钟 2023-07-04 15:42 1阅读 0赞

给定字符串 S 和 T, 计算 S 的所有子序列中有多少个 T.

子序列字符串是原始字符串删除一些(或零个)字符之后得到的字符串, 并且要求剩下的字符的相对位置不能改变. (比如 “ACE” 是 ABCDE 的一个子序列, 而 “AEC” 不是)

样例
    样例 1:
    
    输入: S = "rabbbit", T = "rabbit"
    输出: 3
    解释: 你可以删除 S 中的任意一个 'b', 所以一共有 3 种方式得到 T.
    样例 2:
    
    输入: S = "abcd", T = ""
    输出: 1
    解释: 只有删除 S 中的所有字符这一种方式得到 T
    挑战
    挑战时间复杂度 O(n^2n
    2
     ), 空间复杂度 O(n) 的算法.
    
    如果你不知道如何优化空间, O(n^2n
    2
     ) 的空间复杂度也是可以通过的.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70_pic_center]  
以例子来看，动态规划过程如图  
思路：  
（1）dp【i】【0】都置为1，是因为数组初始化为0，为了在只有一种方式达到子序列的时候，可以让其得到正确的结果。  
（2）双重循环中， dp【i】【j】=dp【i-1】【j】是为了继承子序列在到达第j个字符时可以得到的n种方式，而如果子序列和字符串的某个字符相同时，则需要在dp【i】【j】的基础上再加上子序列达到第j-1字符时候可以得到的n种方式，即dp【i-1】【j-1】才是，子序列在达到第j个字符时真正可以得到的n种方式。

简而言之，就是需要计算字符串删除后，子序列在到达每个字符时的最多的方式数是多少。

class Solution {
        
    public:
        /**
         * @param S: A string
         * @param T: A string
         * @return: Count the number of distinct subsequences
         */
        int numDistinct(string &S, string &T) {
        
            // write your code here
            vector<vector<int>> dp(S.size()+1,vector<int>(T.size()+1,0));
            for (int i = 0; i <= S.size(); i++) {
        
                /* code */
                dp[i][0]=1;
            }
            for (int i = 1; i <=S.size() ; i++) {
        
                /* code */
                for(int j = 1; j <= T.size(); j++)
                {
        
                    dp[i][j]=dp[i-1][j];
                    if(S[i-1]==T[j-1])
                        dp[i][j]+=dp[i-1][j-1];
                }
            }
            return dp[S.size()][T.size()];
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200320151720687.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk4MTMxNQ==,size_16,color_FFFFFF,t_70#pic_center