最小字符數應該添加到字符串迴文的DP方法？

Question

查找製作S迴文所需的最小字符數。例如，如果S = "fft"，字符串應該更改爲字符串"tfft"，只添加1個字符。現在

，我使用了DP辦法解決這個問題，就是如下：

讓定的輸入字符串是S[1.....L]。然後輸入字符串中的任意子S[i....j]，我們可以發現最小插入爲：

• min_insertions(S[i+1 ...... j-1])[if S[i] is equal to S[j]]
• min(min_insertions(S[i+1......j]), min_insertions(S[i....j-1])) + 1

我編寫這個如下：

#include <iostream> 

using namespace std; 

int dp[100][100]; 
int main (void) 
{ 
    int n,i,j; 
    char arr[100]; 
    cin>>arr; 
    n = strlen(arr); 
    //cout<<"You entered the string as "<<arr<<"\n"; 
    for (i = 0; i < n; i++) 
     dp[i][0] = 0; 
    for (i = 0; i < n; i++) 
    { 
     for (j = 0; j < n; j++) 
     { 
      if (arr[i] == arr[j]) 
       dp[i][j] = dp[i+1][j-1]; 
      else 
       dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1; 
     } 
    // cout<<dp[0][n-1]; 
    } 
    cout<<dp[0][n-1]<<"\n"; 
    return 0; 
} 

但是，這給出了一個錯誤的值。爲什麼會發生？例如，如果我輸入字符串abc，則輸出1。這有什麼問題？我的邏輯有什麼問題嗎？

Answer 1

你沒有按照正確的順序填充你的數組dp。例如，dp [0] [2]將要求尚未計算的dp [1] [2]。

所以邏輯應該有以下形式的分配循環：

for (int i = 0; i <n; i++) { 
    for (int h = 0; h < n-i; h++) { 
     dp[i][i+h] = .. // your part 
    } 
} 

您還需要更加註意上面哪裏h = 0，在那裏你不想打電話dp[i+1][i]或dp[i][i-1]的情況下，並且h=1, arr[i]=arr[i+1]您不希望dp[i+1][i]被調用。