代码随想录之动态规划（力扣题号）

62 不同路径

很简单的dp

class Solution {public int uniquePaths(int m, int n) {//58-02int[][] dp = new int[m][n];//初始化for(int i = 0;i<m;i++){dp[i][0] = 1;}for(int i = 0;i<n;i++){dp[0][i] = 1;}for(int i=1;i<m;i++){for(int j = 1;j<n;j++){dp[i][j] = dp[i-1][j]+dp[i][j-1];}}return dp[m-1][n-1];}
}

63 不同路径2

和前一题的区别在于只要判断当前有障碍物就dp对应数值设为0，否则就是正常算法，还有就是初始化的时候要判断前面出现过障碍物就得设为0

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {//05-13int m = obstacleGrid.length;int n = obstacleGrid[0].length;int[][] dp = new int[m][n];int f = 0;for(int i=0;i<m;i++){if(obstacleGrid[i][0]==1){f = 1;dp[i][0] = 0;} if(f==1) dp[i][0] = 0;//自从出现过之后就是0else dp[i][0] = 1;}f = 0;for(int j=0;j<n;j++){if(obstacleGrid[0][j]==1){f = 1;dp[0][j] = 0;} if(f==1) dp[0][j] = 0;else dp[0][j] = 1;}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==0){dp[i][j] = dp[i-1][j]+dp[i][j-1];}else dp[i][j] = 0;}}return dp[m-1][n-1];}
}

343 整数拆分

dp[i]表示拆分整数i能取得的最大乘积
递推表达：选择dp[i-j]*j和(i-j)*j中最大的一个，两个分别表示拆成大于两个和拆成两个

看题解之后觉得容易，但是如果没放在dp章节里也不太好想

class Solution {public int integerBreak(int n) {//06int[] dp = new int[n+1];dp[0] = 0;dp[1] = 1;dp[2] = 1;for(int i=3;i<=n;i++){for(int j=1;j<i;j++){dp[i] = Math.max(dp[i],Math.max(dp[i-j]*j,(i-j)*j));}}return dp[n];}
}

96 不同的二叉搜索树

画图画了很久还是没找到规律，还是因为没有从搜索树的特点出发：总共有i个节点，每次以j为头节点，那左子树的节点有j-1个，右子树的节点的有i-j个，相乘再累加即可！！！

class Solution {public int numTrees(int n) {//14-10int[] dp = new int[n+1];if(n==1) return 1;Arrays.fill(dp,0);dp[0] = 1;dp[1] = 1;dp[2] = 2;for(int i=3;i<=n;i++){for(int j=1;j<=i;j++){//对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加//一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-jdp[i] += dp[j-1]*dp[i-j];}}return dp[n];}
}

背包问题

• 二维数组

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

• 一维数组写法（滚动数组）倒序遍历

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

要注意先遍历物品，再遍历背包容量，然后内层要从大到小！！

int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量 不能改变
for (int i = 0; i < wLen; i++){for (int j = bagWeight; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}
}

416 分割等和子集

第一反应是用双指针，先排序之后从两边往中间指，但是后来发现这是不行的，因为两个集合完全是可以数值交叉的，所以还是需要转成01背包问题（回溯会超时）

class Solution {public boolean canPartition(int[] nums) {//41 不能用双指针因为两个集合可以交叉 像1122是可以的 但是双指针就不行-13int sum = 0;for(int num:nums) sum+=num;if(sum%2==1) return false;int target = sum/2;int[] dp = new int[target+1];Arrays.fill(dp,0);for(int i=0;i<nums.length;i++){for(int j = target;j>=nums[i];j--){dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}return dp[target]==target;}
}

1049 最后一块石头的重量 II

也不好想！！要多思考
可以转换成上一题，就是尽量分成两堆相同的，差值就是剩下的

class Solution {public int lastStoneWeightII(int[] stones) {//16//分成尽量相同的两堆 之后的差值就是最小的int sum = 0;for(int num:stones) sum+=num;int target = sum/2;int[] dp = new int[target+1];for(int i=0;i<stones.length;i++){for(int j=target;j>=stones[i];j--){dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-dp[target]*2;}
}

最后dp[target]就是分成的一堆的数量之和，另一堆的重量就是sum-dp[target], 两堆之差就是sum-dp[target]*2;

494 目标和

用之前的回溯还是有问题，因为不用把具体的列出来，只要计算数字就可以用dp.转换为01背包问题。dp[j]表示装进j容量的包有最多多少种解法

组合类的公式

dp[j] += dp[j - nums[i]]

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum+target<0||sum<target) return 0;//target可能为负 不能过大或过小if((sum+target)%2==1) return 0;int left = (sum+target)/2;int[] dp = new int[left+1];dp[0]=1;for(int i=0;i<nums.length;i++){for(int j = left;j>=nums[i];j--){dp[j]+=dp[j-nums[i]];}}return dp[left];}}

474 0和1

可以转换为01背包问题，就是重量有m和n两个维度，dp[i][j]表示最多由i个0和j个1组成的最大长度

class Solution {public int findMaxForm(String[] strs, int m, int n) {//53int[][] dp = new int[m+1][n+1];//表最多装m个0 n个1dp[0][0]=0;for(String str:strs){//外层 遍历物品int zero = 0;int one = 0;for(int i=0;i<str.length();i++){if(str.charAt(i)=='0') zero++;if(str.charAt(i)=='1') one++;}for(int i=m;i>=zero;i--){//内层 从大到小遍历两个维度的“背包重量”for(int j=n;j>=one;j--){dp[i][j] = Math.max(dp[i][j],dp[i-zero][j-one]+1);}}}return dp[m][n];}
}

518 零钱兑换2

class Solution {public int change(int amount, int[] coins) {//12int[] dp = new int[amount+1];dp[0] = 1;for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
}

377. 组合总和 Ⅳ

完全背包问题的排列数，外层遍历背包，内层遍历物品，都是从小到大遍历

class Solution {public int combinationSum4(int[] nums, int target) {//17-23int[] dp = new int[target+1];dp[0]=1;for(int i=0;i<=target;i++){for(int j=0;j<nums.length;j++){if(i>=nums[j]) dp[i] +=dp[i-nums[j]];}}return dp[target];}
}

爬楼梯问题的进阶版

每次一步可以选择一个台阶，两个台阶，三个台阶，…，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
转换一下就是完全背包问题的排列问题！因为顺序是有关系的

class Solution {public int climbStairs(int n) {int[] dp = new int[n + 1];int[] weight = {1,2,...m};dp[0] = 1;for (int i = 0; i <= n; i++) {for (int j = 0; j < weight.length; j++) {if (i >= weight[j]) dp[i] += dp[i - weight[j]];}}//或者直接for (int i = 1; i <= n; i++) { // 遍历背包for (int j = 1; j <= m; j++) { // 遍历物品if (i - j >= 0) dp[i] += dp[i - j];}}return dp[n];}
}

322 零钱兑换

完全背包问题 注意要把0下标和非0下标的初始化分开

class Solution {public int coinChange(int[] coins, int amount) {//31//完全背包问题 个数int[] dp = new int[amount+1];Arrays.fill(dp,amount+1);//初始化一个最大的dp[0] = 0;//0下标for(int i=0;i<coins.length;i++){for(int j=coins[i];j<=amount;j++){dp[j]=Math.min(dp[j-coins[i]]+1,dp[j]);}}return dp[amount]==amount+1?-1:dp[amount];}
}

279 完全平方数

class Solution {public int numSquares(int n) {//完全背包  49-51int[] dp = new int[n+1];Arrays.fill(dp,n+1);//初始化最大的dp[0]=0;for(int i=1;i*i<=n;i++){for(int j=i*i;j<=n;j++){dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}return dp[n];}
}

139 单词拆分

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {//55 完全背包 跟顺序有关int n = s.length();boolean[] dp = new boolean[n+1];//dp[i]表示0-i下标的s可以被组成的个数dp[0]=true;for(int i=1;i<=s.length();i++){//排列问题 背包在外层for(String str:wordDict){//物品内层int len = str.length();if(i>=len&&dp[i-len]&&s.substring(i-len,i).equals(str)){//递推公式dp[i] = true;}}}return dp[n];}
}

198 打家劫舍

class Solution {public int rob(int[] nums) {//7-12int[] dp = new int[nums.length];dp[0] = nums[0];if(nums.length==1) return nums[0];dp[1] = Math.max(nums[0],nums[1]);for(int i=2;i<nums.length;i++){dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);}return dp[nums.length-1];}
}

213 打家劫舍2

class Solution {public int rob(int[] nums) {//14-20int[] dp = new int[nums.length];int[] dp2 = new int[nums.length];//偷第一家dp[0] = nums[0];if(nums.length==1) return nums[0];dp[1] = nums[0];//第二家就不偷了for(int i=2;i<nums.length;i++){dp[i] = Math.max(dp[i-2]+nums[i],dp[i-1]);}//最后一家不偷 就是dp[nums.length-2]//不偷第一家dp2[0] = 0;dp2[1] = nums[1];for(int i=2;i<nums.length;i++){dp2[i] = Math.max(dp2[i-2]+nums[i],dp2[i-1]);}//选两种中大的return Math.max(dp[nums.length-2],dp2[nums.length-1]);}
}

337 打家劫舍3

树形dp!!!其实和数组一样，就是要确定遍历方式，这里需要用后序遍历，从下往上

/* Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int rob(TreeNode root) {int[] res = af(root);return Math.max(res[0],res[1]);}public int[] af(TreeNode root){int[] res = new int[2];if(root==null) return new int[]{0,0};int[] left = af(root.left);int[] right = af(root.right);//下标0：偷，下标1：不偷   0是选了当前节点值 1是没选res[0] = root.val+left[1]+right[1];res[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);return res;}
}

121 买卖股票的最佳时机

class Solution {public int maxProfit(int[] prices) {//41-44int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;for(int i=0;i<prices.length;i++){if(prices[i]<min) min = prices[i];max = Math.max(max,prices[i]-min);}return max;}
}

122 买卖股票的最佳时机2

class Solution {public int maxProfit(int[] prices) {//47-49int max = 0;if(prices.length==1) return 0;for(int i=1;i<prices.length;i++){max += Math.max(0,prices[i]-prices[i-1]);}return max;}
}

123 买卖股票的最佳时机2

class Solution {public int maxProfit(int[] prices) {//50//下标为1 表示买了一次  2：表示买了一次又卖了一次 3：表示买了两次卖了一次 4：买了两次卖了两次int[][] dp = new int[prices.length][5];dp[0][1] = -prices[0];dp[0][3] = -prices[0];for(int i=1;i<prices.length;i++){dp[i][0] = 0;dp[i][1] = Math.max(dp[i-1][1],dp[i][0]-prices[i]);dp[i][2] = Math.max(dp[i-1][2],dp[i][1]+prices[i]);dp[i][3] = Math.max(dp[i-1][3],dp[i][2]-prices[i]);dp[i][4] = Math.max(dp[i-1][4],dp[i][3]+prices[i]);}return dp[prices.length-1][4];}
}

188

就是上一题的进阶版，把k也用数组表示即可

class Solution {public int maxProfit(int k, int[] prices) {//03-13int[][] dp = new int[prices.length][2*k+1];for(int i=1;i<=2*k;i+=2){dp[0][i] = -prices[0];      }for(int i=1;i<prices.length;i++){dp[i][0] = 0;for(int j=1;j<=2*k;j+=2){dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]-prices[i]);dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i][j]+prices[i]);}}return dp[prices.length-1][2*k];}
}

309. 最佳买卖股票时机含冷冻期

状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
不持有股票状态，这里就有两种卖出股票状态
状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
状态三：今天卖出股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

确定递推公式
达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：

操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
操作二：今天买入了，有两种情况
前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

昨天一定是持有股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

class Solution {public int maxProfit(int[] prices) {//15int n = prices.length;if (n == 0) return 0;int[][] dp = new int[prices.length][4];dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];}return Math.max(dp[n - 1][3], Math.max(dp[n - 1][1], dp[n - 1][2]));}
}

714 买卖股票含手续费

class Solution {public int maxProfit(int[] prices, int fee) {int[][] dp = new int[prices.length][2];// 0 : 持股（买入）// 1 : 不持股（售出）// dp 定义第i天持股/不持股 所得最多现金dp[0][0] = -prices[0];for(int i=1;i<prices.length;i++){dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);}return dp[prices.length-1][1];}
}

740 删除并获得点数

和打家劫舍有点像，不过要求的是相邻的数字 而不是相邻的nums

class Solution {public int deleteAndEarn(int[] nums) {//47 像打家劫舍if(nums.length==1) return nums[0];int[] count = new int[10001];Arrays.fill(count,0);for(int i=0;i<nums.length;i++){count[nums[i]]++;}int[] dp = new int[10001];dp[0] = 0;dp[1] = count[1];for(int i=2;i<dp.length;i++){dp[i] = Math.max(dp[i-1],dp[i-2]+count[i]*i);}return dp[10000];}
}

300. 最长递增子序列

好像过了十几天没刷题，有点生疏，明明指导写法还是改了十几分钟

class Solution {public int lengthOfLIS(int[] nums) {//02-19//前面最长的int[] dp = new int[nums.length];//以i为字符串结尾的最长长度if(nums.length==1) return 1;Arrays.fill(dp,1);int res = -1;for(int i=1;i<nums.length;i++){//找前面的更小的，且dp最大的for(int j=0;j<i;j++){if(nums[i]>nums[j]) dp[i] = Math.max(dp[i],dp[j]+1);}res = Math.max(res,dp[i]);}return res;}
}

718 最长重复子数组

class Solution {public int findLength(int[] nums1, int[] nums2) {//20-40int result = 0;int[][] dp = new int[nums1.length + 1][nums2.length + 1];      for (int i = 1; i < nums1.length + 1; i++) {for (int j = 1; j < nums2.length + 1; j++) {if (nums1[i - 1] == nums2[j - 1]) {//注意如果没有相等就不用管，还是0，因为子数组要求是连续的dp[i][j] = dp[i - 1][j - 1] + 1;result = Math.max(result, dp[i][j]);}}}       return result;}
}

1143 最长公共子序列

class Solution {public int longestCommonSubsequence(String text1, String text2) {//42-47int res = 0;int[][] dp = new int[text1.length()+1][text2.length()+1];//默认初始化为0for(int i=1;i<=text1.length();i++){for(int j=1;j<=text2.length();j++){if(text1.charAt(i-1)==text2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);//不要求连续就需要写这个res = Math.max(res,dp[i][j]);}}return res;//其实最大值一定在最后，所以返回 dp[text1.length()][text2.length()] 也一样}
}

1035 不相交的线

其实就是找最长公共子序列的个数即可

class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {//01-03int[][] dp = new int[nums1.length+1][nums2.length+1];for(int i=1;i<=nums1.length;i++){for(int j=1;j<=nums2.length;j++){if(nums1[i-1]==nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}return dp[nums1.length][nums2.length];}
}

53 最大子数组和

连续子数组

class Solution {public int maxSubArray(int[] nums) {//35-40int[] dp = new int[nums.length];int res = Integer.MIN_VALUE;for(int i=0;i<nums.length;i++){if(i==0) dp[i] = nums[i];else{dp[i] = Math.max(0,dp[i-1])+nums[i];}res = Math.max(res,dp[i]);}return res;}
}

392 判断子序列

class Solution {public boolean isSubsequence(String s, String t) {//42-46int[][] dp = new int[s.length()+1][t.length()+1];for(int i=1;i<=s.length();i++){for(int j=1;j<=t.length();j++){if(s.charAt(i-1)==t.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}if(dp[s.length()][t.length()]==s.length()) return true;else return false;}
}

115 不同的子序列

第一眼没有想出来，还是看了题解，主要是递推公式的变化。因为要求s中包含t，所以递推的时候考虑删掉s中的字符

class Solution {public int numDistinct(String s, String t) {//47int[][] dp = new int[s.length()+1][t.length()+1];for(int i=0;i<s.length();i++){dp[i][0] = 1;}for(int i=1;i<=s.length();i++){for(int j=1;j<=t.length();j++){if(s.charAt(i-1)==t.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];//dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]else dp[i][j] = dp[i-1][j];}}return dp[s.length()][t.length()];}
}

583. 两个字符串的删除操作

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

这里dp数组的定义有点点绕，大家要撸清思路。

确定递推公式
当word1[i - 1] 与 word2[j - 1]相同的时候
当word1[i - 1] 与 word2[j - 1]不相同的时候
当word1[i - 1] 与 word2[j - 1]相同的时候，dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：

情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1

情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1

情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

class Solution {public int minDistance(String word1, String word2) {//01int[][] dp = new int[word1.length()+1][word2.length()+1];//初始化for(int i=0;i<=word1.length();i++){//记得要初始化到len+1位dp[i][0] = i;}for(int i=0;i<=word2.length();i++){dp[0][i] = i;}for(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];else dp[i][j] = Math.min(dp[i-1][j-1]+2,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));}}return dp[word1.length()][word2.length()];}
}

72 编辑距离

class Solution {public int minDistance(String word1, String word2) {//57-05int[][] dp = new int[word1.length()+1][word2.length()+1];for(int i=0;i<=word1.length();i++){dp[i][0] = i;}for(int i=0;i<=word2.length();i++){dp[0][i] = i;}for(int i=1;i<=word1.length();i++){for(int j=1;j<=word2.length();j++){if(word1.charAt(i-1)==word2.charAt(j-1)) dp[i][j] = dp[i-1][j-1];else{dp[i][j] = Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;}}}return dp[word1.length()][word2.length()];}
}

647 回文子串个数

class Solution {int res = 0;public int countSubstrings(String s) {//20 从中心向两边扩展        for(int i=0;i<s.length();i++){func(s,i,i);func(s,i,i+1);}return res;}public void func(String s, int begin, int end){while(begin>=0&&end<s.length()&&begin<=end&&s.charAt(begin)==s.charAt(end)){begin--;end++;res++;            }}
}

最长回文子串

class Solution {public int longestPalindromeSubseq(String s) {//32int res = 0;for(int i=0;i<s.length();i++){res = Math.max(res,Math.max(func(s,i,i),func(s,i,i+1)));}return res;}public int func(String s, int begin, int end){while(begin>=0&&end<s.length()&&begin<=end&&s.charAt(begin)==s.charAt(end)){begin--;end++;}return end-begin-1;}
}

回文子串是要连续的，回文子序列可不是连续的！ 回文子串，回文子序列都是动态规划经典题目。

516 最长回文子序列

class Solution {public int longestPalindromeSubseq(String s) {//32int[][] dp = new int[s.length()][s.length()];for(int i=s.length()-1;i>=0;i--){//递推顺序要从下往上，从左往右dp[i][i]=1;//初始化for(int j=i+1;j<s.length();j++){if(s.charAt(i)==s.charAt(j)) dp[i][j]=dp[i+1][j-1]+2;else{dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);}}}return dp[0][s.length()-1];}}