Question: https://oj.leetcode.com/problems/distinct-subsequences/

Question Name: Distinct Subsequences

This is a dynamic programming challenge. Firstly I solved it with recursion. But that solution did not satisfy the time requirement. These two posts give more details about the right solution: LeetCode: Distinct Subsequences（不同子序列的个数）(in Chinese) and Distinct Subsequences DP explanation (in English).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution: # @return an integer def numDistinct(self, S, T): cache = [0] * (len(T)+1) cache[0] = 1 for indexS in xrange(len(S)): pre = cache[0] for indexT in xrange(len(T)): current = cache[indexT+1] if S[indexS] == T[indexT]: cache[indexT+1] += pre pre = current return cache[-1] |

Well, the algorithm running time can be reduced to half if you can recognize the fact that only half of the matrix needs to be filled, aka triangle matrix.