DP problem
Разница между en1 и en2, 0 символ(ов) изменены
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](https://www.geeksforgeeks.org/count-distinct-subsequences/) 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский kitsune 2020-09-09 13:26:43 24
en2 Английский kitsune 2020-07-22 13:02:14 0 (published)
en1 Английский kitsune 2020-07-22 13:01:18 983 Initial revision (saved to drafts)