leetcode 115. Distinct Subsequences Hard | 115. 不同的子序列（动态规划）

约定不等于承诺〃 2022-10-18 15:49 72阅读 0赞

## 题目 ##

[https://leetcode.com/problems/distinct-subsequences/][https_leetcode.com_problems_distinct-subsequences]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：递归（超时） ####

这种解法比较容易理解，时间复杂度没算出来，但肯定不是 O(m\*n)。提交之后超时了。

> 2021-9-20 09:33:04 补充：根据左神的“从暴力递归到动态规划”，可以给此方法加傻缓存，即可得到动态规划解法。

class Solution { 
        public int numDistinct(String s, String t) { 
            char[] ss = s.toCharArray();
            char[] tt = t.toCharArray();
            int count = count(ss, tt, 0, 0);
            return count;
        }
    
        public int count(char[] ss, char[] tt, int sBegin, int tBegin) { 
            if (tBegin == tt.length) return 1;
            if (sBegin == ss.length) return 0;
            int cnt = 0;
            while (sBegin != ss.length) { 
                if (ss[sBegin] == tt[tBegin]) { 
                    cnt += count(ss, tt, sBegin + 1, tBegin + 1); // 固定当前字母并调子过程
                }
                // 不固定当前字母继续搜索
                sBegin++;
            }
            // System.out.println("cnt2=" + cnt);
            return cnt;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

#### 方法2：动态规划 ####

参考：[https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java][https_leetcode.com_problems_distinct-subsequences_discuss_37327_Easy-to-understand-DP-in-Java]

The idea is the following:

*  we will build an array `mem` where `mem[i+1][j+1]` means that `S[0..j]` contains `T[0..i]` that many times as distinct subsequences. Therefor the result will be `mem[T.length()][S.length()]`.
 *  we can build this array rows-by-rows:
 *  the first row must be filled with 1. That’s because the empty string is a subsequence of any string but only 1 time. So `mem[0][j] = 1` for every `j`. So with this we not only make our lives easier, but we also return correct value if `T` is an empty string.
 *  the first column of every rows except the first must be 0. This is because an empty string cannot contain a non-empty string as a substring – the very first item of the array: `mem[0][0] = 1`, because an empty string contains the empty string 1 time.

So the matrix looks like this:

S 0123....j
    T +----------+
      |1111111111|
    0 |0         |
    1 |0         |
    2 |0         |
    . |0         |
    . |0         |
    i |0         |

From here we can easily fill the whole grid: for each `(x, y)`, we check if `S[x] == T[y]` we add the previous item and the previous item in the previous row, otherwise we copy the previous item in the same row. The reason is simple:

*  if the current character in S **doesn’t equal** to current character T, then we have **the same number** of distinct subsequences as we had without the new character.
 *  if the current character in S **equal** to the current character T, then the distinct number of subsequences = **the same number we had before** plus the distinct number of subsequences we had with **less longer T and less longer S**.

An example:  
`S: [acdabefbc]` and `T: [ab]`

first we check with `a`:

*  *
          S = [acdabefbc]
    mem[1] = [0111222222]

then we check with `ab`:

*  * 
          S = [acdabefbc]
    mem[1] = [0111222222]
    mem[2] = [0000022244]

And the result is 4, as the distinct subsequences are:

S = [a   b    ]
          S = [a      b ]
          S = [   ab    ]
          S = [   a   b ]

See the code in Java:

public int numDistinct(String S, String T) { 
        // array creation
        int[][] mem = new int[T.length()+1][S.length()+1];
    
        // filling the first row: with 1s
        for(int j=0; j<=S.length(); j++) { 
            mem[0][j] = 1;
        }
        
        // the first column is 0 by default in every other rows but the first, which we need.
        for(int i=0; i<T.length(); i++) { 
            for(int j=0; j<S.length(); j++) { 
                if(T.charAt(i) == S.charAt(j)) { 
                    mem[i+1][j+1] = mem[i][j] + mem[i+1][j];
                } else { 
                    mem[i+1][j+1] = mem[i+1][j];
                }
            }
        }
        
        return mem[T.length()][S.length()];
    }

Sure let’s consider the same example as above: `S = [acdabefbc]`, `T = [ab]`

*  * 
          S = [acdabefbc]
    mem[1] = [0111222222]
    mem[2] = [00000222_ ]

Imagine that we are filling the gap at `_`. That means `i=1`, so `T[i] = b` and `j=7`, so `S[j] = b`.

We’re looking for `mem[i+1][j+1]`, which is the place for `_`. Currently we know that at this position we have 2 `a`s before, because `mem[1][7] = 2`, which is the position ABOVE and LEFT to `_`. Also we know that so far we had 2 subsequences before (namely **A**cda**B**ef and acd**AB**ef – highlighted with uppercase) because `mem[2][7] = 2`, which is LEFT to `_`. So having this new `b` would increase the number of subsequences (currently 2) with a number of 2, because it can be matched with the 2 `a`s we saw before. That’s why if `T[i] == S[j]` then `mem[i+1][j+1] := mem[i][j] + mem[i+1][j]`. So `_` will be 4.

##### 总结一下就是：当前 `i, j` 位置不同子序列数量 = 包含当前字母之前的 `[i-1][j-1]` 位置已有的不同子序列数量（之前缺当前字母，所以不是完整的子序列，但由于当前字母相同，所以构成并增加了新的可能情况） + 如果当前字母不相同的话 `[i][j-1]` 位置已经有的的子序列数量（被继承过来作为累加） #####

I hope this helped.

自己实现了一遍：

class Solution { 
        public int numDistinct(String s, String t) { 
            int[][] dp = new int[t.length() + 1][s.length() + 1]; // dp[i][j]表示t[:i]在s[:j]范围内的不同子序列数量
            for (int i = 0; i < s.length() + 1; i++) { 
                dp[0][i] = 1; // "" 是任何序列的子序列
            }
            for (int i = 0; i < t.length(); i++) { 
                dp[i + 1][0] = 0; // "" 不包含任何子序列
                for (int j = 0; j < s.length(); j++) { 
                    if (s.charAt(j) == t.charAt(i)) { 
                        // dp[i+1][j+1] = 不选定当前字母时继承前面已有的子序列数量 + 选定当前字母时与前一个不包含此字母的子序列拼接而产生的新的子序列数量
                        dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j];
                    }else { 
                        dp[i + 1][j + 1] = dp[i + 1][j];
                    }
                }
            }
            return dp[t.length()][s.length()];
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_distinct-subsequences]: https://leetcode.com/problems/distinct-subsequences/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/0df3a75692b4482187ef82e89ca67b89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/58a10c19342b4f87a626bea65cf2755b.png
[https_leetcode.com_problems_distinct-subsequences_discuss_37327_Easy-to-understand-DP-in-Java]: https://leetcode.com/problems/distinct-subsequences/discuss/37327/Easy-to-understand-DP-in-Java
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221005/7d56abdd581740ab8135faf140509e5e.png