DP problem

Revision en2, by kitsune, 2020-07-22 13:02:14

You are given a string $$$s$$$ with length $$$N$$$ and in this problem you should find the number of unique subsequences (not substrings) of the string of every length. eg. find the number of unique subsequences of length $$$1,$$$ then length $$$2, 3 ... N$$$. Answer can be big so print it modulo $$$1e9+7$$$. If the statement is confusing please, see the "explanations" below. I found this post on geeksforgeeks but it counts the total number of distinct subsequences.

Length of the string $$$N<=1000$$$

Example:

Input:

$$$s = dpdp$$$

Output:

$$$2$$$ $$$4$$$ $$$4$$$ $$$1$$$

Explanation:

there are two subsequences of length 1: $$${d, p}$$$

4 subsequences of length 2: $$${dp, dd, pd, pp}$$$

4 subsequences of length 3: $$${dpd, pdp, dpp, ddp}$$$

1 subsequence of length 4: $$${dpdp}$$$

I think it's very easy problem but I have no idea how to solve it. Thanks in advance.

Sorry for my poor English.

Tags #dp, #string, #help, #subsequence, #distinct

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English kitsune 2020-09-09 13:26:43 24
en2 English kitsune 2020-07-22 13:02:14 0 (published)
en1 English kitsune 2020-07-22 13:01:18 983 Initial revision (saved to drafts)