CODEWITHSUNDEEP
dynamic-programmingiteration
Shahriar
Shahriar

Reputation: 13814

How can i convert my recursive DP solution to iterative DP?

Suppose, I have a word "SALADS". I have to find out the number of ways I can remove letters from this word so that it would become a palindrome. Two ways that differ due to order of removing letters are considered the same. Answer for "SALADS" is 15.

I've solve it using recursive DP.

string S;
int DP[65][65];

int DFS(int l, int r)
{
    if(l==r) return 1;
    if(l>r) return 0;

    if(DP[l][r]!=-1) return DP[l][r];

    DP[l][r]=0;

    if(S[l]==S[r])
    {
       return DP[l][r] = 1 + DFS(l+1, r) + DFS(l, r-1);
    }
    else
    {
       return DP[l][r] = DFS(l+1, r) + DFS(l, r-1) - DFS(l+1, r-1);
    }
}

int main()
{
    S = "SALADS";
    DFS(0, S.size()-1);
}

How can i solve this problem using iterative DP?

Upvotes: 2

Views: 713

Answers (1)

Ali Akber
Ali Akber

Reputation: 3800

Try this ->
May be this will work :

long long dp[MAX][MAX];
long long solve(string str)
{
    int n = str.size();
    int i, j;
    memset(dp,0,sizeof(dp));

    for(i=n; i>0; i--)
        for(j=i; j<=n; j++)
            dp[i][j]=(str[i-1]==str[j-1] ? 1+dp[i+1][j]+dp[i][j-1] : dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]);

    return dp[1][n];
}

Upvotes: 1

Related Questions