Please explain the recurrence

#1

Please explain the recurrence

#2

Please go through the editorial
It very well explained
also i have added explanation in the post so that u can understand it better
The editorial has simple and undertandable example ,I`ll reiterate over those examples so that the code becomes easier to understand

string ABCDEFG
Subsequences of size 0 : 1 {} empty string
dp[0] = 1;
then size 1 : dp[1] ?? \ {} , A , dp[1] = 2;
size 2 : dp[2] ?? || {}, A , B , AB dp[2] = 4;
size 3 : dp[3] ??? \ {},A , B , C, AB ,AC , BC, ABC dp[3] = 8

so we a pattern dp[i] = dp[i-1]*2;

but then we have duplicate occurance of characters in the string
here we see a case

stirng : ABCB
{},A , B , C, AB ,AC , BC, ABC , CB , BB ,__ AB__ , __ B __
those with ’ __ ’ mark are the duplicate subsequences , so we see that 2 duplicate subsequence happen

for this the editorial says we mark the position where a character has previously occured, if so we
get a formula

dp[i] = 2* dp[i-1] - dp[pos[i]];
pos[i] is the position where the character last occured.
in this case B occured at 1
do dp[1] is subtracted;
dp[4] = 2* 8 - dp[1] = 14