记忆化搜索和动态规划 --最长回文子串为例

记忆化搜索

记忆化搜索是一种优化递归算法的方法，通过将已经计算过的子问题的结果存储起来（通常使用哈希表或数组），避免重复计算相同的子问题。
本质上是通过缓存中间结果来减少计算的重复性。

动态规划

动态规划是通过将问题分解成子问题来解决的，它通常通过表格化的方式（自底向上）来存储子问题的解，以便在需要时能够快速访问。
动态规划的核心思想是通过自底向上的方式来解决问题，通常使用一个数组或表格来存储每个子问题的解，从而避免了递归的重复计算。

二者区别与联系

记忆化搜索和动态规划的区别，主要在于计算的顺序。
记忆化搜索通常是自顶向下的递归方式，在递归中检查子问题是否已经计算过，并存储结果。
动态规划通常是自底向上的方式，逐步计算所有子问题，并存储所有的中间结果，最终得到问题的解。
两者的时间复杂度是相同的，都是 O(n)，因为两者都避免了重复计算子问题。

例题

最长回文子串 -力扣

记忆化搜索解答：

class Solution {
public:int dp[1000][1000];std::string ss;bool judge(int l, int r) {if (dp[l][r] != -1) {return dp[l][r];}if (ss[l] == ss[r]) {if (r - l > 1) {if (dp[l + 1][r - 1] == -1) {dp[l][r] = judge(l + 1, r - 1);} else {dp[l][r] = dp[l + 1][r - 1];}} else {dp[l][r] = 1;}} else {dp[l][r] = 0;}return dp[l][r];}std::string longestPalindrome(std::string s) {memset(dp,-1,sizeof(dp));int len = s.length();ss = s;int res = 0;int l = 0;for (int i = 0; i < len; i++) {for (int j = i; j < len; j++) {dp[i][j] = judge(i, j);if (dp[i][j] == 1 && j - i > res) {res = j - i;l = i;}}}return s.substr(l, res + 1);}
};

动态规划解答

class Solution {
public:std::string longestPalindrome(std::string s) {int len = s.length();bool dp[1000][1000];memset(dp,false,sizeof(dp));for(int i = len - 1; i >= 0; i--){for(int j = i; j < len; j++){if(s[i] != s[j]){dp[i][j] = false;}else{if(i == j){dp[i][j] = true;}else{if(j - i == 1){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}}}}int res = 0;int l = 0;for(int i = 0; i < len; i++){for(int j = i; j < len; j++){if(dp[i][j] == true){if(res < j - i){res = j - i;l = i;}}}}return s.substr(l,res + 1);}};

由于函数调用的原因，使用递归的记忆化搜索算法的时间会稍微久一点