力扣，516. 最长回文子序列，动态规划+记忆化回溯_力扣 记忆性回溯

力扣，516. 最长回文子序列
https://leetcode-cn.com/problems/longest-palindromic-subsequence/

先说下记忆化回溯这个想法比较简单，对于i,j之间最长的回文子序列我们记做f(i,j),显然是有
if s[i]==s[j] ,f(i,j)=f(i+1,j-1)+2,
else f(i,j)= max(f(i+1,j),f(i,j-1))
所以如果按照思路直接写递归的话很简单。

####那么问题来了，这样如果不加@lru_cache(None)会超时，这是python提供的lru功能，来自functools 模块
####他可以记录递归中计算过的结果。就相当于他把最近计算过的结果都存了起来可以直接调用。
####如果不用这个，我们也可以自己定义字典取实现它，当然自己写的肯定是没有别人的模块效果，功能齐全的
from functools import lru_cache
@lru_cache(None)
def rec(i,j,s):
     if i>j:
         return 0
     if i==j:
         return 1
     if s[i] == s[j]:
         return rec(i+1,j-1,s) + 2
     else:
         return max(rec(i+1,j,s),rec(i,j-1,s))
 return rec(0,len(s)-1,s)
#####就像下面一样
lru = dict()
def rec(i,j,s):
     if i>j:
         return 0
     if i==j:
         return 1
     if s[i] == s[j]:
     	 tmp = rec(i+1,j-1,s)
     	 lru[(i+1,j-1)] = tmp
         return tmp + 2
     else:
     	tmp1 = rec(i+1,j,s)
     	tmp2 = rec(i,j-1,s)
     	lru[(i+1,j)] = tmp1
     	lru[(i,j-1)] = tmp2
        return max(tmp1,tmp2)
 return rec(0,len(s)-1,s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

这题还可以用动态规划来做下，我们来分析下递推方程，
if s[i]==s[j] ,f(i,j)=f(i+1,j-1)+2, （1）
else f(i,j)= max(f(i+1,j),f(i,j-1)) （2）
对于（1）来说，f(i,j)来自于i+1列，j-1行，也就是说第i+1列，j-1行的值要比i列，j行早更新，并且i>j的，所以最终的遍历顺序应该是i从后往前,j从i+1往后。

n= len(s)
dpc = [[0 for j in range(n)]for i in range(n)]
dpc[n-1][n-1] = 1####这里i是从倒数第二个开始的，最后一个值要先赋值，为1
 for i in range(n-2,-1,-1):
     dpc[i][i] = 1 
     for j in range(i+1,n):
         if s[j] == s[i]:                
             dpc[i][j] = 2 + dpc[i+1][j - 1]
         else:
             dpc[i][j] = max(dpc[i + 1][j], dpc[i][j - 1])
 # print(dpc)
 return dpc[0][n - 1]
1
2
3
4
5
6
7
8
9
10
11
12

其实这题还是递归好写一点，动态规划要想好方向。