动态规划算法题总结（十七）—— 动态规划（下）
198、打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
1、确定dp数组（dp table）以及下标的含义
dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2、确定递推公式
决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，
（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点，因为前面都是最大值了，所以递推出来也是最大值，）
然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3、dp数组如何初始化
从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：dp[1] = max(nums[0], nums[1]);
class Solution {
public int rob(int[] nums) {
int[] dp=new int[nums.length];
if(nums.length==1)
return nums[0];
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++)
{
//一个是不取i 一个取i
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[nums.length-1];
}
}
213、打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
对于一个数组，成环的话主要有如下三种情况：
- 情况一：考虑不包含首尾元素
- 情况二：考虑包含首元素，不包含尾元素
- 情况三：考虑包含尾元素，不包含首元素
注意我这里用的是"考虑"，例如情况三，虽然是考虑包含尾元素，但不一定要选尾部元素！ 对于情况三，取nums[1] 和 nums[3]就是最大的。
而情况二 和 情况三 都包含了情况一了，所以只考虑情况二和情况三就可以了。
class Solution {
private int rob1(int[] nums,int start, int end) {
int n=end-start+1;
int[] dp=new int[n];
if(n==1)
return nums[start];
dp[0]=nums[start];
dp[1]=Math.max(nums[start],nums[start+1]);
for(int i=2;i<n;i++)
{
//一个是不取i 一个取i
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i+start]);
}
return dp[n-1];
}
public int rob(int[] nums) {
int n=nums.length;
if(n==1)
return nums[0];
//分两段来看
int num1=rob1(nums,0,n-2);
int num2=rob1(nums,1,n-1);
return num1>num2 ? num1:num2;
}
}
337、打家劫舍 III
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 *在不触动警报的情况下 ，小偷能够盗取的最高金额* 。
示例 1:
输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
树形结构一定要先想到遍历方式，本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。
与198.打家劫舍，213.打家劫舍II一样，关键是要讨论当前节点抢还是不抢。
如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）
这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解。
这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组，其实这里的返回数组就是dp数组，每个结点有一个状态数组。
下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
// 3.状态标记递归
// 执行用时：0 ms , 在所有 Java 提交中击败了 100% 的用户
// 不偷：Max(左孩子不偷，左孩子偷) + Max(右孩子不偷，右孩子偷)
// root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
// Math.max(rob(root.right)[0], rob(root.right)[1])
// 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
// root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
public int rob3(TreeNode root) {
int[] res = robAction1(root);
return Math.max(res[0], res[1]);
}
int[] robAction1(TreeNode root) {
int res[] = new int[2]; //每个结点都有一个结果
if (root == null)
return res;
//后续遍历
int[] left = robAction1(root.left);
int[] right = robAction1(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
}
121、买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
贪心算法
因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
class Solution {
public int maxProfit(int[] prices) {
// 找到一个最小的购入点
int low = Integer.MAX_VALUE;
// res不断更新，直到数组循环完毕
int res = 0;
for(int i = 0; i < prices.length; i++){
low = Math.min(prices[i], low);
res = Math.max(prices[i] - low, res);
}
return res;
}
}
动态规划
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int length = prices.length;
// dp[i][0]代表第i天持有股票的最大收益
// dp[i][1]代表第i天不持有股票的最大收益
int[][] dp = new int[length][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
}
return dp[length - 1][1];
}
}
122、 买卖股票的最佳时机 II
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
本题和上一题的唯一区别是本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）
所以唯一不同的地方就是，当天持有股票但是前一天不持有股票的递推公式，这正是因为本题的股票可以买卖多次！ 所以买入股票的时候，可能会有之前买卖的利润即：dp[i - 1] [1]，所以dp[i - 1] [1] - prices[i]。
class Solution {
public int maxProfit(int[] prices) {
int len =prices.length;
//dp[i][0]代表第i天的时候持有股票，的最大收益
//dp[i][1]代表第i天不持有股票的最大收益
int[][] dp=new int[len][2];
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<len;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]);
}
return dp[len-1][1]; //不持有股票的收益最大
}
}
贪心算法：只要每天的利润是正的，就加在一起。
class Solution {
public int maxProfit(int[] prices) {
//数组记录利润
int[] profit=new int[prices.length-1];
int result=0;
for(int i=0;i<prices.length-1;i++)
{
profit[i]=prices[i+1]-prices[i];
}
for(int i=0;i<profit.length;i++)
{
if(profit[i]>0)
result+=profit[i];
}
return result;
}
}
123、 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。
接来下我用动态规划五部曲详细分析一下：
1、确定dp数组以及下标的含义
一天一共就有五个状态
- 没有操作 （其实我们也可以不设置这个状态）
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
dp[i] [j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i] [j]表示第i天状态j所剩最大现金。
需要注意：dp[i] [1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
// 边界判断, 题目中 length >= 1, 所以可省去
if (prices.length == 0) return 0;
/*
* 定义 5 种状态:
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
*/
int[][] dp = new int[len][5];
dp[0][1] = -prices[0];
// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
dp[0][3] = -prices[0];
for (int i = 1; i < len; i++) {
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
return dp[len - 1][4];
}
}
188、买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
class Solution {
public int maxProfit(int k, int[] prices) {
//k次，说明需要第一次买，第一次卖，。。。。
// [天数][股票状态]
// 股票状态: 奇数表示第 k 次交易持有状态, 偶数表示第 k 次交易不持有状态, 0 表示没有操作
int len =prices.length;
int[][] dp=new int[len][2*k+1];
//初始化,没初始化的都为0
for(int i=1;i<2*k;i+=2)
{
dp[0][i]=-prices[0];
}
for(int i=1;i<len;i++)
{
for(int j=1;j<2*k;j+=2)
{
//j是奇数，代表持有
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
//j+1是偶数，代表不持有
dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]+prices[i]);
}
}
return dp[len-1][2*k];
}
}
309、买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
- 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
具体可以区分出如下四个状态：
- 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
- 不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
为什么不持有股票的状态，要分开。因为本题我们有冷冻期，而冷冻期的前一天，只能是 「今天卖出股票」状态，如果是 「不持有股票状态」那么就很模糊，因为不一定是 卖出股票的操作。
class Solution {
public int maxProfit(int[] prices) {
int len =prices.length;
int[][] dp=new int[len][4];
//设置四种状态:
//0:持有股票状态（状态一）
//1:达到保持卖出股票状态（状态二）,即不持有股票
//2:达到今天就卖出股票状态（状态三）
//3:达到冷冻期状态（状态四）
dp[0][0]=-prices[0];
for(int i=1;i<len;i++)
{
dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][1]-prices[i],dp[i-1][3]-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[len-1][1],Math.max(dp[len-1][2],dp[len-1][3]));
}
}
714、买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
本题和动态规划：122.买卖股票的最佳时机II (opens new window)的区别就是这里需要多一个减去手续费的操作。
lass Solution {
public int maxProfit(int[] prices, int fee) {
//只考虑卖出时支付手续费
int len=prices.length;
int[][] dp = new int[len][2];
//初始化
dp[0][0]=-prices[0];
dp[0][1]=0;
for(int i=1;i<len;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[len-1][1];
}
}
股票问题总结
300、最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
如果if (nums[i] > nums[j])，位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
class Solution {
public int lengthOfLIS(int[] nums) {
int len =nums.length;
int[] dp =new int[len];
Arrays.fill(dp,1);
int result=1;
for(int i=1;i<len;i++)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
{
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
if(dp[i]>result)
result=dp[i]; //，最大值有可能在中间，把最大值记录下来
}
return result;
}
}
674、 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
因为是连续的，所以i只需要与前一个元素进行比较。如果不是递增，则跳出循环，dp[i] 为1，重新从i开始计
概括来说：不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关。
class Solution {
public int findLengthOfLCIS(int[] nums) {
int len =nums.length;
int dp[] =new int[len];
Arrays.fill(dp,1);
int result=1;
for(int i=1;i<len;i++)
{
if(nums[i]>nums[i-1])
{
dp[i]=dp[i-1]+1;
}
if(dp[i]>result)
{
result=dp[i];
}
}
return result;
}
}
718、最长重复子数组
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
注意子数组要求是连续的！也就是说，dp[i]一定是以i为结尾的数组
1、dp[i] [j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i] [j]
使用这种定义，初始化很方便。
2、即当A[i - 1] 和B[j - 1]相等的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1;
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int 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]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
result = Math.max(result, dp[i][j]);
}
}
}
return result;
}
}
1、dp[i] [j] ：以下标i为结尾的A，和以下标j 为结尾的B，最长重复子数组长度为dp[i] [j]
2、即当A[i - 1] 和B[j - 1]相等的时候，dp[i] [j] = dp[i - 1] [j - 1] + 1;
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp=new int[nums1.length][nums2.length];
int result =0;
//初始化
for(int i=0;i<nums1.length;i++)
if(nums1[i]==nums2[0])
{
dp[i][0]=1;
result=1;
}
for(int i=0;i<nums2.length;i++)
if(nums2[i]==nums1[0])
{
dp[0][i]=1;
result=1;
}
for(int i=1;i<nums1.length;i++)
{
for(int j=1;j<nums2.length;j++)
{
if(nums1[i]==nums2[j]) //如果不相等，dp[i]就为0了
{
dp[i][j]=dp[i-1][j-1]+1;
}
if(dp[i][j]>result)
result=dp[i][j];
}
}
return result;
}
}
两种方式，因为for循环里的i和j都是从1开始的，所以第一种定义是可以计算下标为0的数组的值的，但是第二种定义因为直接表示的是下标为i 和 j 的 最长重复子数组的长度，所以下标为0的，要先初始化。
1143、最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
本题和动态规划：718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了，但要有相对顺序
不连续，以为可以删除一些字符，也可以不删除，所以可以不包括i，只是i之前的部分。
1、定义：dp[i] [j]：长度为[0, i]的字符串text1与长度为[0, j]的字符串text2的最长公共子序列为dp[i] [j]
2、确定递推公式
主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i] [j] = dp[i - 1] [j - 1] + 1;
如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
即：dp[i] [j] = max(dp[i - 1] [j], dp[i] [j - 1]);
因为是相对顺序，所以还要考虑上面第二种情况。
定义：dp[i] [j]：长度为[0, i]的字符串text1与长度为[0, j]的字符串text2的最长公共子序列为dp[i] [j]
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] char1=text1.toCharArray();
char[] char2=text2.toCharArray();
int[][] dp=new int[char1.length][char2.length];
//注意dp的初始化
for(int i=0;i<char1.length;i++)
{
if(char1[i]==char2[0])
{
dp[i][0]=1;
for(int j=i;j<char1.length;j++)
{
dp[j][0]=1;
}
break;
}
}
for(int i=0;i<char2.length;i++)
{
if(char2[i]==char1[0])
{
dp[0][i]=1;
for(int j=i;j<char2.length;j++)
{
dp[0][j]=1;
}
break;
}
}
for(int i=1;i<char1.length;i++)
{
for(int j=1;j<char2.length;j++)
{
if(char1[i]==char2[j])
{
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[char1.length-1][char2.length-1];
}
}
定义：dp[i] [j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i] [j]
这个时候初始化，因为dp[i] [0]是和空串比较，所以是0。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] char1=text1.toCharArray();
char[] char2=text2.toCharArray();
int[][] dp=new int[char1.length+1][char2.length+1];
//dp[i]定义为1到i的时候边界初始化比较复杂
for(int i=1;i<=char1.length;i++)
{
for(int j=1;j<=char2.length;j++)
{
if(char1[i-1]==char2[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[char1.length][char2.length];
}
}
总结：判断两个数组或者字符串公共的，就要使用dp[i] [j] 来表示 i-1 和j-1
1035、不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
- nums1[i] == nums2[j]
- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3
思路：直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; 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[len1][len2];
}
}
53、最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
贪心算法：
因为是连续的，所以当和为负的时候，就起的是负作用，所以重新开始计算。
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==1)
return nums[0];
int result =Integer.MIN_VALUE;
int count=0;
for(int i=0;i<nums.length;i++)
{
count+=nums[i];
result=Math.max(result,count);
if(count<0)
{
count=0; //如果值为负的，直接count为0，i从下一个开始计算。
continue; //这个也可以不加
}
}
return result;
}
}
动态规划：
dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。
确定递推公式
dp[i]只有两个方向可以推出来：
- dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
- nums[i]，即：从头开始计算当前连续子序列和
一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i])
注意最后的结果可不是dp[nums.size() - 1]！ ，而是dp[6]。
在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。
那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。
所以在递推公式的时候，可以直接选出最大的dp[i]。
public static int maxSubArray(int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
res = res > dp[i] ? res : dp[i];
}
return res;
}
392、判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，“ace”是“abcde”的一个子序列，而“aec”不是）
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
这道题应该算是编辑距离的入门题目，所以掌握本题的动态规划解法是对后面要讲解的编辑距离的题目打下基础。
1、确定dp数组（dp table）以及下标的含义
dp[i] [j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i] [j]。
这样表示就是方便初始化！
涉及到两个字符串的时候，都要用这种定义，方便初始化。
2、确定递推公式
在确定递推公式的时候，首先要考虑如下两种操作，整理如下：
- if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出现了
- if (s[i - 1] != t[j - 1])
- 相当于t要删除元素，继续匹配
if (s[i - 1] == t[j - 1])，那么dp[i] [j] = dp[i - 1] [j - 1] + 1;，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1] [j-1]的基础上加1（如果不理解，在回看一下dp[i] [j]的定义）
if (s[i - 1] != t[j - 1])，此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i] [j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，即：dp[i] [j] = dp[i] [j - 1];
其实这里 大家可以发现和 1143.最长公共子序列 (opens new window)的递推公式基本那就是一样的，区别就是 本题 如果删元素一定是字符串t，而 1143.最长公共子序列 是两个字符串都可以删元素。
3、dp数组如何初始化
从递推公式可以看出dp[i] [j]都是依赖于dp[i - 1] [j - 1] 和 dp[i] [j - 1]，所以dp[0] [0]和dp[i] [0]是一定要初始化的。
这里大家已经可以发现，在定义dp[i] [j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i] [j]。
因为这样的定义在dp二维矩阵中可以留出初始化的区间，如图：
如果要是定义的dp[i] [j]是以下标i为结尾的字符串s和以下标j为结尾的字符串t，初始化就比较麻烦了。
dp[i] [0] 表示以下标i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0. dp[0] [j]同理。
class Solution {
public boolean isSubsequence(String s, String t) {
int len1=s.length();
int len2=t.length();
char[] char1=s.toCharArray();
char[] char2=t.toCharArray();
int[][] dp=new int[len1+1][len2+1];
for(int i=1;i<=s.length();i++)
{
for(int j=1;j<=t.length();j++) //注意这里要用等号
{
if(char1[i-1]==char2[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else
dp[i][j]=dp[i][j-1];
}
}
if(dp[len1][len2]==len1) //用长度来判断，相同子序列的长度，如果等于len1，说明s是t的子序列
return true;
else
return false;
}
}
双指针法
class Solution {
public boolean isSubsequence(String s, String t) {
int len1=s.length();
int len2=t.length();
char[] char1=s.toCharArray();
char[] char2=t.toCharArray();
int sum=0;
int i=0;
int j=0;
while(i<len1 && j<len2)
{
if(char1[i]==char2[j])
{
i++;
j++;
sum++;
}
else{
j++;
}
}
if(sum==len1)
return true;
else
return false;
}
}
115、不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
这道题目相对于72. 编辑距离，简单了不少，因为本题相当于只有删除操作，不用考虑替换增加之类的。
但相对于刚讲过的动态规划：392.判断子序列 (opens new window)就有难度了，这道题目双指针法可就做不了了，来看看动规五部曲分析如下：
1、确定dp数组（dp table）以及下标的含义
dp[i] [j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i] [j]。即有多少种删除操作可以把s变成t。
2、确定递推公式
这一类问题，基本是要分析两种情况
- s[i - 1] 与 t[j - 1]相等
- s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时，dp[i] [j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1] [j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1] [j-1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1] [j]。
这里可能有录友不明白了，为什么还要考虑 不用s[i - 1]来匹配，都相同了指定要匹配啊。
例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。
所以当s[i - 1] 与 t[j - 1]相等时，dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j];
当s[i - 1] 与 t[j - 1]不相等时，dp[i] [j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1] [j]
所以递推公式为：dp[i] [j] = dp[i - 1] [j];
3、dp数组如何初始化
从递推公式dp[i] [j] = dp[i - 1] [j - 1] + dp[i - 1] [j]; 和 dp[i] [j] = dp[i - 1] [j]; 中可以看出dp[i] [j] 是从上方和左上方推导而来，如图：，那么 dp[i] [0] 和dp[0] [j]是一定要初始化的。
每次当初始化的时候，都要回顾一下dp[i] [j]的定义，不要凭感觉初始化。
dp[i] [0]表示什么呢？
dp[i] [0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。
那么dp[i] [0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
再来看dp[0] [j]，dp[0] [j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。
那么dp[0] [j]一定都是0，s如论如何也变成不了t。
最后就要看一个特殊位置了，即：dp[0] [0] 应该是多少。
dp[0] [0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。
class Solution {
public int numDistinct(String s, String t) {
char[] char1 =s.toCharArray();
char[] char2=t.toCharArray();
int len1=s.length();
int len2=t.length();
int [][] dp=new int[len1+1][len2+1];
for(int i=0;i<=len1;i++)
{
dp[i][0]=1;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(char1[i-1]==char2[j-1])
{
dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
}
else
{
dp[i][j]=dp[i-1][j];
}
}
}
return dp[len1][len2];
}
}
583、两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
动态规划一：
本题和动态规划：115.不同的子序列 (opens new window)相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。
这次是两个字符串可以相互删了，这种题目也知道用动态规划的思路来解，动规五部曲，分析如下：
1、确定dp数组（dp table）以及下标的含义
dp[i] [j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。
2、确定递推公式
- 当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]的情况。
当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});
因为 dp[i] [j - 1] + 1 = dp[i - 1] [j - 1] + 2，所以递推公式可简化为：dp[i] [j] = min(dp[i - 1] [j] + 1, dp[i] [j - 1] + 1);
这里可能不少录友有点迷糊，从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1]，dp[i] [j-1] 本来就不考虑 word2[j - 1]了，那么我在删 word1[i - 1]，是不是就达到两个元素都删除的效果，即 dp[i] [j-1] + 1。
3、dp数组如何初始化
从递推公式中，可以看出来，dp[i] [0] 和 dp[0] [j]是一定要初始化的。
dp[i] [0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i] [0] = i。
dp[0] [j]的话同理，所以代码如下：
// dp数组中存储需要删除的字符个数
class Solution {
public int minDistance(String word1, String word2) {
char[] char1 =word1.toCharArray();
char[] char2= word2.toCharArray();
int len1=word1.length();
int len2=word2.length();
int[][] dp=new int[len1+1][len2+1];
for(int i=0;i<=len1;i++)
{
dp[i][0]=i;
}
for(int j=0;j<=len2;j++)
{
dp[0][j]=j;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(char1[i-1]==char2[j-1])
{
dp[i][j]=dp[i-1][j-1];
}
else
{
dp[i][j]=Math.min(dp[i-1][j]+1,dp[i][j-1]+1);
}
}
}
return dp[len1][len2];
}
}
思路二：
本题和动态规划：1143.最长公共子序列 (opens new window)基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。
class Solution {
//和1143最长公共子序列相同
public int minDistance(String word1, String word2) {
char[] char1=word1.toCharArray();
char[] char2=word2.toCharArray();
int len1=char1.length;
int len2=char2.length;
int[][] dp=new int[len1+1][len2+1];
//dp[i]定义为1到i的时候边界初始化比较复杂
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(char1[i-1]==char2[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 len1+len2-2*dp[char1.length][char2.length];
}
}
72、编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
dp[i] [j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i] [j]。
if (word1[i - 1] == word2[j - 1])
不操作 //dp[i][j]=dp[i-1][j-1];
if (word1[i - 1] != word2[j - 1])
增 //dp[i][j] = dp[i][j-1] + 1; word1增加元素其实就是word2删除元素
删 //dp[i][j] = dp[i - 1][j] + 1; //word删除元素
换 //dp[i][j] = dp[i - 1][j - 1] + 1;
class Solution {
public int minDistance(String word1, String word2) {
int len1=word1.length();
int len2=word2.length();
int[][] dp=new int[len1+1][len2+1];
//初始化
for(int i=0;i<=len1;i++)
{
dp[i][0]=i;
}
for(int i=0;i<=len2;i++)
{
dp[0][i]=i;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;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],Math.min(dp[i][j-1],dp[i-1][j]))+1;
}
}
}
return dp[len1][len2];
}
}
647、回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
1、确定dp数组（dp table）以及下标的含义
如果大家做了很多这种子序列相关的题目，在定义dp数组的时候 很自然就会想题目求什么，我们就如何定义dp数组。
绝大多数题目确实是这样，不过本题如果我们定义，dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系。
dp[i] 和 dp[i-1] ，dp[i + 1] 看上去都没啥关系。
所以我们要看回文串的性质。 如图：
我们在判断字符串S是否是回文，那么如果我们知道 s[1]，s[2]，s[3] 这个子串是回文的，那么只需要比较 s[0]和s[4]这两个元素是否相同，如果相同的话，这个字符串s 就是回文串。
那么此时我们是不是能找到一种递归关系，也就是判断一个子字符串（字符串的下表范围[i,j]）是否回文，依赖于，子字符串（下表范围[i + 1, j - 1]）） 是否是回文。
所以为了明确这种递归关系，我们的dp数组是要定义成一位二维dp数组。
布尔类型的dp[i] [j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i] [j]为true，否则为false。
2、确定递推公式
在确定递推公式时，就要分析如下几种情况。
整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。
当s[i]与s[j]不相等，那没啥好说的了，dp[i] [j]一定是false。
当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况
- 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
- 情况二：下标i 与 j相差为1，例如aa，也是回文子串
- 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1] [j - 1]是否为true。
即
if (s[i] == s[j]) {
if (j - i <= 1) { // 情况一 和 情况二
result++;
dp[i][j] = true;
} else if (dp[i + 1][j - 1]) { // 情况三
result++;
dp[i][j] = true;
}
}
3、dp数组如何初始化
dp[i] [j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。
所以dp[i] [j]初始化为false。
4、确定遍历顺序
遍历顺序可有有点讲究了。
首先从递推公式中可以看出，情况三是根据dp[i + 1] [j - 1]是否为true，在对dp[i] [j]进行赋值true的。
dp[i + 1] [j - 1] 在 dp[i] [j]的左下角，如图：
如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1] [j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
所以一定要从下到上，从左到右遍历，这样保证dp[i + 1] [j - 1]都是经过计算的。
5、举例，
输入：“aaa”，dp[i] [j]状态如下：
图中有6个true，所以就是有6个回文子串。
注意因为dp[i] [j]的定义，所以j一定是大于等于i的，那么在填充dp[i] [j]的时候一定是只填充右上半部分
class Solution {
public int countSubstrings(String s) {
char[] chars =s.toCharArray();
int len=chars.length;
boolean[][] dp=new boolean[len][len];
int result=0;
for(int i=len-1;i>=0;i--)
{
for(int j=i;j<len;j++)
{
if(chars[i]==chars[j])
{
if(j-i<=1)
{
result++;
dp[i][j]=true;
}
else if(dp[i+1][j-1])
{
dp[i][j]=true;
result++;
}
}
}
}
return result;
}
}
5、最长回文子串
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
最长回文子串，在判断是否为回文子串的基础上，记录最长的回文子串，并记录这个子串。
class Solution {
public String longestPalindrome(String s) {
char[] chars=s.toCharArray();
int len =chars.length;
boolean[][] dp=new boolean[len][len];
int maxlen=1; //记录最长的回文子串的长度
String ans=chars[0]+""; //String必须被初始化
for(int i=len-1;i>=0;i--)
{
for(int j=i;j<len;j++)
{
if(chars[i]==chars[j])
{
if(j-i<=1)
{
dp[i][j]=true;
if((j-i+1)>maxlen)
{
maxlen=j-i+1;
ans=s.substring(i,j+1);
}
}
else if(dp[i+1][j-1])
{
dp[i][j]=true;
if((j-i+1)>maxlen)
{
maxlen=j-i+1;
ans=s.substring(i,j+1);
}
}
}
}
}
return ans;
}
}
516、最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb"
我们刚刚做过了 动态规划：回文子串 (opens new window)，求的是回文子串，而本题要求的是回文子序列， 要搞清楚这两者之间的区别。
回文子串是要连续的，回文子序列可不是连续的！ 回文子串，回文子序列都是动态规划经典题目。
1、确定dp数组（dp table）以及下标的含义
dp[i] [j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i] [j]。
2、确定递推公式
在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。
如果s[i]与s[j]相同，那么dp[i] [j] = dp[i + 1] [j - 1] + 2;
如图： 
（如果这里看不懂，回忆一下dp[i] [j]的定义）
如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
加入s[j]的回文子序列长度为dp[i + 1] [j]。
加入s[i]的回文子序列长度为dp[i] [j - 1]。
那么dp[i] [j]一定是取最大的，即：dp[i] [j] = max(dp[i + 1] [j], dp[i] [j - 1]);
3、dp数组如何初始化
首先要考虑当i 和j 相同的情况，从递推公式：dp[i] [j] = dp[i + 1] [j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况，即当i和j相等的时候使用递推公式计算出来的是不对的。
所以需要手动初始化一下，当i与j相同，那么dp[i] [j]一定是等于1的，即：一个字符的回文子序列长度就是1。
其他情况dp[i] [j]初始为0就行，这样递推公式：dp[i] [j] = max(dp[i + 1] [j], dp[i] [j - 1]); 中dp[i] [j]才不会被初始值覆盖。
4、确定遍历顺序
从递归公式中，可以看出，dp[i] [j] 依赖于 dp[i + 1] [j - 1] ，dp[i + 1] [j] 和 dp[i] [j - 1]，如图：
所以遍历i的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的。
5、举例推导dp数组
输入s:“cbbd” 为例，dp数组状态如图：
class Solution {
public int longestPalindromeSubseq(String s) {
char[] chars = s.toCharArray();
int len=s.length();
int[][] dp=new int[len][len];
for(int i=len-1;i>=0;i--)
{
dp[i][i]=1;
for(int j=i+1;j<len;j++)
{
if(chars[i]==chars[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][len-1];
}
}
32、最长有效括号
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0
class Solution {
public int longestValidParentheses(String s) {
int result=0;
char[] chars =s.toCharArray();
int len=s.length();
int[] dp=new int[len];
for(int i=1;i<len;i++)
{
if(chars[i]==')')
{
if(chars[i-1]=='(')
{
dp[i]=(i>2?dp[i-2]:0)+2;
}
else if(i-dp[i-1]>0 &&chars[i-dp[i-1]-1]=='(')
{
if(i-dp[i-1]>=2)
{
dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2];
}
else{
dp[i]=dp[i-1]+2;
}
}
}
result=Math.max(result,dp[i]);
}
return result;
}
}
class Solution {
public int longestValidParentheses(String s) {
int result=0;
Deque<Integer> stack =new LinkedList<>();
stack.push(-1);
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='(')
stack.push(i);
//说明是右括号
else
{
stack.pop();
if(stack.isEmpty())
stack.push(i);
else
result=Math.max(result,i-stack.peek());
}
}
return result;
}
}
动态规划总结
原文地址：https://blog.csdn.net/maruofan666/article/details/142994612
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！