115. Distinct Subsequences

# Hard 太难了

Two-sequence DP problem. It's easy to define distinct[i][j], which means how many distinct ways from s[:i] to t[:j]. But how to compute distinct[i][j] according to distinct[i-1[j], distinct[i][j-1] and distinct[i-1][j-1] is difficult to have an idea.

Solution:

1. Initilize distinct[i][j], set empty row and column. distinct[0][0]=1, from s[i] to NULL is 1, from NULL to t[j] is 0.

2. If s[i] = t[j], then distinct[i][j]=distinct[i-1][j-1]+distinct[i-1][j], think this with drawing.

3. If s[i] != t[j], then distinct[i][j]=distinct[i-1][j-1].

4. Return distinct[len(s)][len(t)].

Python

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        # distinct[i][j], means how many distinct ways can generate from s[:i] to t[:j]
        # initilize distinct[i][j]
        distinct = [[0]*(len(t)+1) for i in range(len(s)+1)]
        
        distinct[0][0] = 1
        for i in range(1, len(s)+1):
            distinct[i][0] = 1
        for j in range(1, len(t)+1):
            distinct[0][j] = 0
            
        for i in range(1, len(s)+1):
            for j in range(1, len(t)+1):
                if s[i-1] == t[j-1]:
                    distinct[i][j] = distinct[i-1][j] + distinct[i-1][j-1]
                else:
                    distinct[i][j] = distinct[i-1][j]

        return distinct[len(s)][len(t)]

Java

distinct[i][j] 与distinct[i][j-1]没有任何关系。

这种题最重要的思维是找二维数组distinct[i][j] 与前面的 distinct[i-1][j], distinct[i][j-1], disintct[i][j] 中的谁有直接关系，并且有什么逻辑联系。