leetcode516. 最长回文子序列

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-subsequence

题目描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = “bbbab”
输出：4
解释：一个可能的最长回文子序列为 “bbbb” 。

示例 2：
输入：s = “cbbd”
输出：2
解释：一个可能的最长回文子序列为 “bb” 。

提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成

暴力递归

解题思路

采用指针法：
一个指针卡住左边，一个卡住右边。
递归法去比较，
base case: 入股左右指针相遇，单个字符肯定是回文，返回1.
递归状况时：
左指针和右指针字符相同，那就同时移动一位。回文长度加2.
不等时，要分左指针移动，和右指针移动两种情况，
最后我们取几种情况的最大值。

代码演示

 public static int longestPalindromeSubseq(String s) {if (s == null || s.length() == 0){return 0;}int[][] ans = new int[s.length()][s.length()];return process(s.toCharArray(),0,s.length()-1,ans);// return process(s.toCharArray(),0,s.length()-1);}/*** 递归* @param s 字符数组* @param L 左指针* @param R 右指针* @return*/public static int process(char[] s,int L,int R){//base caseif(L > R){return 0;}//base case 单个字符肯定是回文  返回1if(L == R){return 1;}int p1 = 0;int p2 = 0;int p3 = 0;//相等时 同时移动if(s[L] == s[R]){p1 = 2 + process(s,L + 1,R - 1);}else{//不等时分两种情况，最后要最大值p2 = process(s,L + 1,R);p3 = process(s,L,R - 1);}return Math.max(p1,Math.max(p2,p3));}

递归 + 缓存

解题思路

递归中有太多的重复计算，我们加到缓存中，减少计算量
要根据变量来确定如何加缓存，
变量是L 和 R ，因此用二维数组来缓存

代码演示

 public static int longestPalindromeSubseq(String s) {if (s == null || s.length() == 0){return 0;}int[][] ans = new int[s.length()][s.length()];return process(s.toCharArray(),0,s.length()-1,ans);// return process(s.toCharArray(),0,s.length()-1);}/*** 递归加 缓存* @param s 字符数组* @param L 左指针* @param R 右指针* @param dp 缓存表* @return*/public static int process(char[] s,int L,int R,int[][]dp){//base caseif(L > R){return 0;}if(L == R){return 1;}//缓存中有的话 直接缓存拿if(dp[L][R] != 0){return dp[L][R];}int p1 = 0;int p2 = 0;int p3 = 0;if(s[L] == s[R]){p1 = 2 + process(s,L + 1,R - 1,dp);}else{p2 = process(s,L + 1,R,dp);p3 = process(s,L,R - 1,dp);}int ans = Math.max(p1,Math.max(p2,p3));//结果加到缓存中dp[L][R] = ans;return ans;}

动态规划

解题思路

动态规划就是对递归j加缓存方案的改写
三个步骤
1.根据base case 去初始化缓存表，
2.把递归过程改成从递归缓存表中拿值的过程
3.返回值就是调用递归的最初始状态的值。

代码演示

 /*** 动态规划* @param s* @return*/public static int dp(String s){char[] chars = s.toCharArray();int N = chars.length;int[][] ans = new int[N][N];//base case 去初始化for (int i = 0; i < N ;i++){ans[i][i] = 1;}//根据递归过程去填值for (int i = 1;i < N ;i++){int R = i;int L = 0;while (R < N){int p1 = 0;int p2 = 0;int p3 = 0;if (chars[L] == chars[R]){p1 = 2 + ans[L + 1][R - 1];}else{p2 = ans[L + 1][R];p3 = ans[L][R - 1];}ans[L][R] = Math.max(p1,Math.max(p2,p3));L++;R++;}}//返回调用的最初始状态。return ans[0][N - 1];}

动态规划专题

leetcode1143. 最长公共子序列

leetcode.486. 预测赢家

动态规划.背包问题–填满背包的最大价格

leetcode–N 皇后 II