Solution to Distinct Subsequences by LeetCode

7 Jul

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).

One thought on “Solution to Distinct Subsequences by LeetCode

  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.

Leave a Reply

Your email address will not be published. Required fields are marked *