最長回文子序列問題：
C ：
類解決方案{
上市：
vector<vector<int>> dp;
Solution(){
dp = vector<vector<int>>(1001, vector<int>(1001, -1));
}
int lps(string s, int i, int j){
if(i == j)
return 1;
if(i>j)
return 0;
if(dp[i][j] != -1)
return dp[i][j];
if(s[i] == s[j])
return dp[i][j]= 2 lps(s, i 1, j-1);
else
return dp[i][j]= max(lps(s,i 1,j), lps(s,i,j-1));
}
int longestPalindromeSubseq(string s) {
return lps(s, 0, s.size()-1);
}
};
給 TLE
Python代碼：
類解決方案（物件）：
def lps(self, s, i, j, dp):
if i == j:
return 1
if i> j:
return 0
if dp[i][j] != -1:
return dp[i][j];
if s[i] == s[j]:
dp[i][j]= 2 self.lps(s, i 1, j-1, dp)
else:
dp[i][j]= max(self.lps(s, i 1, j, dp), self.lps(s, i, j-1, dp))
return dp[i][j]
def longestPalindromeSubseq(self, s):
dp = [[-1 for x in range(len(s))] for y in range(len(s))]
ans= self.lps(s, 0, len(s) -1, dp)
return ans
通過 leetcode 中的所有測驗用例。誰能幫我理解這種行為？
提前致謝。
uj5u.com熱心網友回復：
在 C 版本中，您在函式中按值傳遞字串。（即，每個函式呼叫都會生成一個新的字串副本）。
在 python 版本中，因為默認情況下字串是不可變的，所以它們是通過參考傳遞的。
因此，要使您的代碼在 C 中作業，只需執行int lps(string& s, int i, int j)
string &s這里確保字串通過參考傳遞。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/513462.html
標籤：递归动态规划
上一篇：我終于理解了遞回還是我錯了？