Doubt in DP

help
1

https://leetcode.com/problems/interleaving-string/
There are 3 changing variables in this but still 2D memoization is giving correct answer. Can any one explain why so?
2D memoization

int dp[101][101];
bool sol(string s1,string s2,string s3,int n1,int n2,int k)
{
    if(n1<0)
    {
        string str=s2.substr(0,n2+1);
        string str1=s3.substr(0,k+1);
        return str==str1;
    }
    if(n2<0)
    {
        string str=s1.substr(0,n1+1);
        string str1=s3.substr(0,k+1);
        return str==str1;
    }
    if(dp[n1][n2]!=-1)
        return dp[n1][n2];
    if(s3[k]==s1[n1]&&sol(s1,s2,s3,n1-1,n2,k-1)||s3[k]==s2[n2]&&sol(s1,s2,s3,n1,n2-1,k-1))
    {
        return dp[n1][n2]=true;
    }
    else
    {
        return dp[n1][n2]=false;
    }
}
bool isInterleave(string s1, string s2, string s3) {
    memset(dp,-1,sizeof(dp));
    if(s1.length()+s2.length()!=s3.length())
        return false;
    return sol(s1,s2,s3,s1.length()-1,s2.length()-1,s3.length()-1);
}

3D memoization

    bool sol(string s1,string s2,string s3,int n1,int n2,int n3)
    {
        if(n3<0)
            return true;
        if(n1<0)
        {
            string str=s2.substr(0,n2+1);
            string str1=s3.substr(0,n3+1);
            return str==str1;
        }
        if(n2<0)
        {
            string str=s1.substr(0,n1+1);
            string str1=s3.substr(0,n3+1);
            return str==str1;
        }
        if(dp[n1][n2][n3]!=-1)
            return dp[n1][n2][n3];
        if(s1[n1]==s2[n2]&&s1[n1]==s3[n3])
        {
            return dp[n1][n2][n3]=sol(s1,s2,s3,n1-1,n2,n3-1)||sol(s1,s2,s3,n1,n2-1,n3-1);
        }
        else if(s1[n1]==s3[n3])
        {
            return dp[n1][n2][n3]=sol(s1,s2,s3,n1-1,n2,n3-1);
        }
        else if(s2[n2]==s3[n3])
        {
            return dp[n1][n2][n3]=sol(s1,s2,s3,n1,n2-1,n3-1);
        }
        else
        {
            return dp[n1][n2][n3]=false;
        }
    }
2

It is because in above approach , dp[i][j] = whether we can make prefix of s3 string of length(i+j+2) using i length of s1 and j length of s2 string, and it will only depend on s1 and s2 and not on s3 index clearly (because for dp[i][j], index of s3 will be (i+j+2) only in interleaving string)…so there is no need of taking third index of s3 as third state.

1 Like