Kaavi and Magic Spell

We will first make a dp[i][j] $$$\rightarrow$$$ No of ways to make the last j words of the prefix T using the first i letters of S.

Now it is clear , $$$dp[i][j] = 0$$$ if $$$i \lt j$$$
Let's think about the other states.
if we have the ith element from S , that will either go to the front or to the back of A , Now if if matches the jth letter from the end of T , then we can do that. The other thing we can do, is send to the back. Now here arises a problem , on sending it to the back there can arise two possibilities , it is counted in the prefix T or it is not. Now we can see it will be counted as the last letter of the Prefix T $$$\text{iff}$$$ $$$i=j$$$ , else we can freely put it on the back.

So now we have

So the only state we have a Problem in Calculating is $$$dp[i][i]$$$

To Calculate that , let's define another dp $$$dp2[i][point]$$$ = No of ways to make $$$\text{T[point point+1 .... point+i-1]}$$$ (Basically the $$$i$$$ length substring of $$$T$$$ starting from Point) using the first $$$i$$$ letters of S.

$$$dp2[i][point] = dp2[i-1][point]\text{ (if S[i] matches the T[i+point-1] ) }+ dp[i][point+1]\text{ (if s[i] matches the T[point] )}$$$

So now we can easily say $$$dp[i][i] = dp2[i][m-i+1]$$$ , and we have calculated our answer.

Solution

Proof of Problem E , DP — Solution

abs(dp[i]-dp[i-1])<=x
assume worst case dp[i-1]=x+val,dp[i]=val
dp[(i-1)*2]=x+val+y
dp[i*2]=val+y
now using dp[i*2] to calculate dp[(i-1)*2] we get dp[(i-1)*2]=val+y+x+x
assume another worst case dp[i-1]=val, dp[i]=x+val
dp[(i-1)*2]=val+y
dp[i*2]=val+y+x
now using dp[i*2] to calculate dp[(i-1)*2] we get dp[(i-1)*2]=val+y+x+x+x
as you can see in both case it is always unoptimal to subtract >=2 times