Reputation: 13814
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
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