How to solve the problem using dynamic programming
Count subsequence problem
@Faizan-Ali-1395131367301898 hey in dp approach,
Let countSub(n) be count of subsequences of
first n characters in input string. We can
recursively write it as below.
countSub(n) = 2*Count(n-1) - Repetition
If current character, i.e., str[n-1] of str has
not appeared before, then
Repetition = 0
Else:
Repetition = Count(m)
Here m is index of previous occurrence of
current character. We basically remove all
counts ending with previous occurrence of
current character.
If there are no repetitions, then count becomes double of count for n-1 because we get count(n-1) more subsequences by adding current character at the end of all subsequences possible with n-1 length.
If there repetitions, then we find count of all distinct subsequences ending with previous occurrence. This count can be obtained be recursively calling for index of previous occurrence.
Hope you get approach.
I am not clear with yor algorithm can please elaborate
@Faizan-Ali-1395131367301898 ye recurrence relation hai countSub(n) = 2*Count(n-1) - Repetition
this is because If there are no repetitions, then count becomes double of count for n-1 because we get count(n-1) more subsequences by adding current character at the end of all subsequences possible with n-1 length.
If there repetitions, then we find count of all distinct subsequences ending with previous occurrence. This count can be obtained be recursively calling for index of previous occurrence.
So make dp array where dp[i] represent no of subsequ of length i.
@Faizan-Ali-1395131367301898 at line 17 of your code update your dp[i+1] as (dp[i+1]+mod)%mod in case if dp[i+1] becomes negative.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.