I found the following problem very interesting on a recent Hackerrank contest, I don't get the intuition for what the editorialist states.It would indeed be very helpful if someone helps me understand it.↵
↵
[Link to the problem](https://www.hackerrank.com/contests/codeagon/challenges/number-of-ways-1/problem)↵
↵
What I got is as follows:↵
↵
(Note:dp[x...y] means dp[x] + dp[x+1] ... + dp[y])↵
↵
for number of ways of reaching a solution from either string a or string b, ↵
the recurrence may go as follows↵
↵
↵
dp[i][j][k][0] = summation of dp[i-1][j-1][k][0...2];↵
↵
dp[i][j][k][1] = (if a[i] equals c[k] then summation of dp[i-1][j][k-1][0...2] else 0) + dp[i-1][j][k][0...2]; ↵
↵
dp[i][j][k][2] = (if b[j] equals c[k] then summation of dp[i][j-1][k-1][0...2] else 0) + dp[i][j-1][k][0...2];↵
↵
↵
Here, dp[i][j][k][x] means number of ways of forming c[0...k] from a[0...i] or from b[0...j] or both.↵
↵
↵
where x = 0 if we neglect last character of both a and b↵
↵
x = 1 if we consider last character of a and not b↵
↵
x = 2 if we consider last character of b and not a↵
↵
Please correct me if I am wrong.Thanks in advance for the help.
↵
[Link to the problem](https://www.hackerrank.com/contests/codeagon/challenges/number-of-ways-1/problem)↵
↵
What I got is as follows:↵
↵
(Note:dp[x...y] means dp[x] + dp[x+1] ... + dp[y])↵
↵
for number of ways of reaching a solution from either string a or string b, ↵
the recurrence may go as follows↵
↵
↵
dp[i][j][k][0] = summation of dp[i-1][j-1][k][0...2];↵
↵
dp[i][j][k][1] = (if a[i] equals c[k] then summation of dp[i-1][j][k-1][0...2] else 0) + dp[i-1][j][k][0...2]; ↵
↵
dp[i][j][k][2] = (if b[j] equals c[k] then summation of dp[i][j-1][k-1][0...2] else 0) + dp[i][j-1][k][0...2];↵
↵
↵
Here, dp[i][j][k][x] means number of ways of forming c[0...k] from a[0...i] or from b[0...j] or both.↵
↵
↵
where x = 0 if we neglect last character of both a and b↵
↵
x = 1 if we consider last character of a and not b↵
x = 2 if we consider last character of b and not a↵
↵
Please correct me if I am wrong.Thanks in advance for the help.
