爲什麼我在這個函數中出現越界異常？

Question

#include <iostream> 
#include <string> 
#include <algorithm> 
using namespace std; 

int findpali (string s,int dp[][100],int st, int e); 
int main (void) 
{ 
    string s; 
    cin>>s; 
    int dp[100][100]; 
    for (int i = 0; i < 100; i++) 
     for (int j = 0; j < 100; j++) 
      dp[i][j] = -1; 
    int out = findpali(s,dp,0,s.length()-1); 
    cout<<out<<"\n"; 
    return 0; 
} 



int findpali (string s,int dp[][100],int st, int e) // st ->starting position, e -> ending position 
    { 
     if (s.length() == 1) 
     { 
      dp[st][e] = 1; 
      return 1; 
     } 
     else if (s.length()==2 && s[st] == s[e]) 
     { 
      dp[st][e] = 2; 
      return 2; 
     } 
     else if (dp[st][e] != -1) 
      return dp[st][e]; 
     else if (s[st] == s[e]) 
     { 
      dp[st][e] = findpali(s.substr(st+1,s.length()-2),dp,st+1,e-1)+2; 
      return dp[st][e]; 
     } 
     else 
     { 
      dp[st][e] = max(findpali(s.substr(st,s.length()-1),dp,st,e-1),findpali(s.substr(st+1,s.length()-1),dp,st+1,e)); 
      return dp[st][e]; 
     } 
    } 

上面的函數查找給定字符串中最長迴文的長度。我已經將給定的數組dp初始化爲-1，然後我將不同的值存儲在數組中。但是，當我輸入一個像ABCD這樣的字符串時，它說出了異常並且中止。這可能是什麼原因？謝謝！

Answer 1

您需要在函數的開始處爲空字符串添加測試。另外，您正在爲原始string s存儲dp，因此當您使用s的子串更新它時，結果不再有效。每次您遞歸調用函數時，您都可以通過不同的索引st and e。

修改後的功能可能是這個樣子：

int findpali(string &s, int dp[][100], int st, int e) 
{ 
    if(s.length()==0 || st > e) { //extra test for boundary case 
     return 0; 
    } 
    if(st==e) // length 1 substring 
    { 
     dp[st][e]=1; 
     return 1; 
    } else if(e-st==1 && s[st] == s[e]) // length 2 substring 
    { 
     dp[st][e]=2; 
     return 2; 
    } else if(dp[st][e] != -1) 
     return dp[st][e]; 
    else if(s[st] == s[e]) 
    { 
     dp[st][e]=findpali(s, dp, st+1, e-1)+2; 
     return dp[st][e]; 
    } else 
    { 
     dp[st][e]=max(findpali(s, dp, st, e-1), findpali(s, dp, st+1, e)); 
     return dp[st][e]; 
    } 
}