如何將遞歸DP解決方案轉換爲迭代DP？

Question

假設，我有一個詞「沙拉」。我必須找出我可以從這個詞中刪除字母的方法的數量，以便它成爲一個迴文。由於刪除字母的順序而有兩種不同的方式被認爲是相同的。 「SALADS」的答案是15.

我已經使用遞歸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); 
} 

如何使用迭代DP解決此問題？

Answer 1

試試這個 - >
可能這將工作：

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]; 
}