0-1背包问题：
分割等和子集
给定背包容量，能不能装满背包，装满了返回true，装不满返回false
最后一块石头的重量II
给定背包容量，尽可能装，求背包中能装的最大重量
目标和
给定背包容量，装满背包有多少种方法
这道题的关键点就是将nums数组分成left和right两个部分分别代表加+号的、加-号的，计算出left子集的背包数量是(sum + target)/2是重中之重。
问题转化为：背包容量为left时，装满背包有多少种方法。
初始化dp[0]=1
递推公式dp[j] += dp[j – num[i]];
遍历顺序：先遍历物品，再遍历背包容量，01背包问题内层遍历要倒序遍历。
一和零
01背包的两维问题。给定背包容量，装满这个背包最多有多少个物品
dp数组的创建:dp[i][j]表示装i个0，j个1的背包，最多能背dp[i][j]个物品。
两个维度来形容物品的重量。
常规的01背包问题递推公式为
dp[j] = Math.max(dp[j], dp[j – weights[i]] + values[i]);
这道题的递推公式为
dp[i][j] = Math.max(dp[i][j], dp[i – x][j – y] + 1);
其中x和y分别表示给的字符串数组中每个元素中的0的个数和1的个数。通过x和y两个维度来形如weight[i]
初始化：dp[0][0]=0，其他的值默认初始化为0
01背包遍历数组必须先遍历物品再遍历背包，同时背包要倒序遍历，为的就是物品只能使用一次。
在这道题中，遍历的物品就是字符串数组中每个字符串，每个字符串有x个0和y个1
背包容量有两层，一个0的个数，一个是1的个数。
综上：本题中物品就是strs里的字符串，背包容量就是描述的m和n
动归五部曲
1、dp[j]表示背包容量为j的时候，背包背的最大价值为dp[j]
2.确定递推公式
3.初始化dp[0]
4.遍历顺序
5.打印dp数组
完全背包与01背包最大的区别就是，一个物品能不能无限取，具体体现在代码上就是内层循环需不需要倒序遍历。
01背包需要倒序遍历，完全背包不需要倒序遍历。
完全背包问题：
与01背包的不同是每种物品都有无限件。
完全背包的递推公式一维数组写法
dp[j] = Math.max(dp[j], d[j – weight[i]] + value[i]);与01背包一样
遍历顺序：两个for循环的先后顺序，都不影响计算dp[j]所需要的值
完全背包代码模板：
int[] dp = new int[bagWeight + 1];
//初始化dp数组都为默认0
for(int i = 0; i < weight.length; i++){//先遍历物品
for(int j = weight[i]; j <= bagWeight; j++){//再遍历背包容量
dp[j] = Math.max(dp[j], dp[j – weight[i]] + value[i]);
}
}
return dp[bagWeight];
题目稍稍有点变化，就会体现在遍历顺序上，所以完全背包题型主要改变在遍历顺序上。
以下两个代码块是解决完全背包问题下的：给定背包容量，装满这个背包的装法数量（分为求组合数和求排列数）主要区别是遍历顺序的不同，求组合数先遍历物品再遍历背包容量，求排列数先遍历背包容量再遍历物品。
//先遍历物品再遍历背包 用来解决求组合数
int[] dp = new int[bagWeight +1];
//初始化，背包容量为0初始化为1，其它初始化为0
dp[0]=1;
for(int i = 0; i < weight.length; i++){//先遍历物品
for(int j = weight[i]; j <= bagWeight; j++){//再遍历背包容量
dp[j] += dp[j – weight[i]];
}
}
return dp[bagWeight];
//先遍历背包再遍历物品 用来求排列数
int[] dp = new int[bagWeight +1];
//初始化，背包容量为0初始化为1，其它初始化为0
dp[0]=1;
for(int j = 0; j <= bagWeight; j++){//先遍历背包容量
for(int i = 0； i < weight.length; i++){//再遍历物品
if(j >= weight[i]){ dp[j] += dp[j – weight[i]];
}
}
}
return dp[bagWeight];
零钱兑换II
完全背包问题+装满背包求组合数装法
给定背包容量，问有多少种装法可以装满背包（要区分装法是求组合数还是排列数）
这里要记住对于装满背包装法初始化时要将dp[0] = 1即背包容量为0时的方法是1
求有多少种装法的动归问题有三个主要的点：
1.初始化时dp[0] = 1，表示背包容量为0的时候有1种装法
2.递推公式dp[j] += dp[j – weight[i]];
3.遍历顺序，对于完全背包问题内存循环不需要倒序遍历，而01背包问题需要倒序遍历
组合总和IV
完全背包问题+装备背包求排列数装法
给定背包容量，问有多少种装法可以装满背包
零钱兑换
完全背包问题+装满背包最少用多少件物品
动归五部曲
1.dp[j]表示背包容量为j（题目中总金额amount）时，装满这个背包所需要的最少物品数为dp[j]（题目中coins硬币的数量，注意这里是硬币数量，不是硬币价值）。
2.递推公式
dp[j] = Math.min(dp[j], dp[j – coins[i]] + 1);
3.初始化
dp[0] = 0; 非0下标初始化，本题取最小值，所以初始为最大值dp[j] = Integer.MAX_VALUE;
4.遍历顺序
因为本题求的是最少装多少件物品，不管是组合装还是排列装，该是几个就是几个，所以不需要考虑物品和背包容量的遍历先后问题。
本题还有一个特殊情况，如果有凑不成的情况出现，必须判断不装coins[i]时，容量为dp[j – coins[i]]的背包装满需要的最少硬币数是不是默认给的Integer.MAX_VALUE，如果是说明不合规，不能用于min赋值；如果不是，那么才可以进行min赋值。
还是标注一下，如果说赋值的时候有MAX_VALUE，那么在MIN求解的时候要判断有没有凑不成的情况。
for(int i = 0; i < weight.length; i++){//先遍历物品 for(int j = weight[i]; j <= bagWeight; j++){//再遍历背包容量
if(dp[j – weight[i]] != Integer.MAX_VALUE){
dp[j] = Math.min(dp[j], dp[j – weight[i]] + 1);
}
}
}
return dp[bagWeight] == Integer.MAX_VALUE ? -1 : dp[bagWeight];
最后判断的dp[amount]是不是Integer.MAX_VALUE，下述实例2的情况，要返回-1。
示例 2：
- 输入：coins = [2], amount = 3
- 输出：-1
5.打印
完全平方数
换汤不换药，给定背包容量，装满这个背包所需要的最少物品数量。(只不过不需要判断“凑不出”的情况，因为最坏也是可以通过1来装出结果）
单词拆分
完全背包+给定背包容量，判断能不能装满这个背包，能装满返回true，不能装满返回false
本题重点是要确定背包容量是什么，用字符串s的长度i作为背包容量。
1.dp[i]表示字符串长度为i时，能不能装满这个背包，能装满dp[i]就为true，不能装满dp[i]就为false。
所以dp[i]数组是布尔类型的。
2.递推公式
if([j, i] 这段字符串在字典集合wordDict中存在 && dp[j] == true){
dp[i] = true;
}else{
dp[i] =false;
}
3.初始化
dp[0] = true;因为在递推公式中要用到dp[0]才能向后推导，所以必须设为true
其它的都设置为false。
4.遍历顺序
因为要求的s是对排列的字符串有顺序的，所以这道题是排列装，因此要先遍历背包容量，再遍历物品。
1.dp[j]表示背包容量为j时，是否能装满这个背包
对应这道题，背包容量用字符串长度来形容，所以dp[j]的含义表示为字符串长度为j时，是否能装满这个背包，如果能装满dp[j]为true；如果不能装满dp[j]为false。
2.递推公式
找到dp[j]的前一个状态是在字符串位置j之前的i位置，所以抽象来看是dp[j] = [i, j] + dp[i]。所以递推公式如下：
if([i, j] 范围的字符串属于wordDict集合 && dp[i] == true){
dp[j] = true;
}
3.初始化
dp[0] = true;因为递推公式中dp[j]需要依赖dp[i]的状态，且i < j，所以dp[0]必须为true，才能推导下去
其它dp[]都默认初始化为false。
4.遍历顺序
因为装填的物品组合需要确定的顺序才能真正构成所需要的字符串s，所以是排列装。因此先遍历背包容量，再遍历物品
for(int j = 1; j <= s.length(); j++){//先遍历背包容量,这里j从1开始是因为背包容量非空（字符串s非空）
for(int i = 0; i < j; i++){//再遍历物品，这里这样写为什么是在遍历物品？因为i是小于j的，从i到j截取的这一段字符串是我们要判断的字符串，判断它在不在wordDict列表中
if(wordDict.contains(s.substring(i, j)) && dp[i] == true){
dp[j] = true;
}
}
}
return dp[s.length()];
5.打印dp
打家劫舍问题：
198.打家劫舍
1.确定dp[j]的含义
dp[j]表示考虑下标j以内（包括j）的房屋，最多可以偷窃的金额为dp[j]。
int[] dp = new int[nums.length];
2.确定递推公式
dp[j]状态的得到是：偷第j个房间dp[j – 2] + nums[j]以及不偷第j个房间，转而考虑偷第j-1房间dp[j-1]
所以：dp[j] = Math.max(dp[j-2] + nums[j], dp[j-1]);
3.初始化
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
4.确定遍历顺序
for(int j = 2; j < dp.length; j++){
dp[j] = Math.max(dp[j-2] + nums[j], dp[j-1]);
}
Return dp[nums.length – 1];
213.打家劫舍II
房间成环，考虑三种情况
方案一：首尾都不偷；方案二：只偷首元素，不偷尾元素；方案三：只偷尾元素，不偷首元素
方案二和方案三已经包含了方案一，所以总的来说只有两个方案。
两个方案处理，所以自定义一个函数robRange(int[] nums, int start, int end)；
遵从左闭右开原则
337.打家劫舍III
树形dp问题
自定义robTree(TreeNode cur){}表示当前节点偷还是不偷所达到的最大金额，所以这个函数的返回值是dp数组。
这里dp数组定义为：大小为2，dp[0]表示不偷当前节点，所拿到的最大金额；d[1]表示偷当前节点，所拿到的最大金额。
遍历二叉树问题：本题使用后序遍历二叉树
递归三部曲：
1.确定返回值类型和传入参数
2.确定终止条件
3.确定递归逻辑
//确定返回值类型和传入参数
Public int[] robTree(TreeNode cur){
if(cur == null){
//终止条件，当前节点为空节点，那么返回dp数组，值都初始化为0
return new int[2];
}
//确定递归逻辑
//后序遍历
两个数组是后一步再考虑的:
int[] leftdp = robTree(cur.left);//左节点
int[] rightdp = robTree(cur.right);//右节点
这一步先考虑 ：//当前节点
//偷当前节点所能拿到的最大金额为：
int val1 = cur.value + leftdp[0] + rightdp[0];//偷了当前节点，那么它的左右孩子节点就不能再偷了，所以要加上左右孩子各自的不偷的最大金leftdp[0]、rightdp[0]。
//不偷当前节点，那么就看左孩子节点要不要偷（看leftdp[0]和leftdp[1]谁更大来决定左孩子节点偷不偷），以及右孩子节点要不要偷（看rightdp[0]和rightdp[1]谁更大来决定右孩子节点偷不偷）
int val2 = Math.max(leftdp[0], leftdp[1]) + Math.max(rightdp[0], rightdp[1]);
return new int[]{val2, val1};
}
在主函数中调用robTree()
int[] result = robTree(root);
return Math.max(result[0], result[1]);
买卖股票问题：
121.买卖股票的最佳时机
只能买卖一次股票
1.dp[i][0]表示第i天持有股票的最大金额，dp[i][1]表示第i天不持股的最大金额。
这样定义可以不遗漏状态。dp[i][0]表示第i天持有股票的最大金额，不仅表示第i天把股票买下来，还可以表示前i天的某一天把股票买下来。dp[i][1]表示第i天不持股的最大金额，不仅表示第i天把股票卖出，还可以表示前i天的某一天把股票卖出。
用户初始的金额一定是0，那么第一次买入股票后，总金额一定是负数。
2.递推公式
dp[i][0]由两个状态推导出：一个是第i-1天持有股票的最大金额dp[i-1][0]；一个是前i-1天都没有买入股票，是第i天才买入的股票，即第i天买入股票的最大金额-price[i]。
所以dp[i][0] = Math.max(dp[i-1][0], -price[i]);
dp[i][1]由两个状态推导出：一个是第i-1天不持股的最大金额dp[i-1][1]；一个是前i-1天都持有股，但是在第i天才卖出，即第i天卖出股票的最大金额为dp[i-1][0]+price[i]。
所以dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + price[i]);
3.初始化
dp[0][0]=-price[0];
dp[0][1]=0;
4.dp[i][0]和dp[i][1]都依赖i-1天的状态，所以正常遍历即可
5.打印dp
122.买卖股票的最佳时机II
可以无限次买卖股票
1.dp[i][0]表示第i天持有股票的最大金额，dp[i][1]表示第i天不持股的最大金额
2.递推公式
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]);
3.初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
4.遍历顺序
5.打印
123.买卖股票的最佳时机III
至多两次买卖股票
//一天五个状态
//0.没有操作
//1.第一次持有股票
//2.第一次卖出股票
//3.第二次持有股票
//4.第二次卖出股票
dp[i][j]中 i表示第i天，j为 [0 – 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金
//递推公式
//dp[i][1]表示第i天第一次持有股票的总金额
//dp[i][1]状态由以下两个状态得到
//1.i-1天都没有持有股票，在第i天买入了股票 dp[i-1][0] – prices[i]
//2.i-1天的某一天持有股票，在第i天什么都不操作 dp[i-1][1]
//所以dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] – prices[i]);
//dp[i][2]表示第i天第一次卖出股票的总金额
//dp[i][2]状态由以下两个状态得到
//1.i-1天内都持有股票，在第i天卖出股票 dp[i-1][1] + prices[i]
//2.i-1天内的某一天卖出了股票，第i天什么都不做 dp[i-1][2]
//所以dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);
//dp[i][3]表示第i天第二次买入股票的总金额
//dp[i][3]状态由以下两个状态得到
//1.i-1天内都没有买入股票（并且进行过一次买卖了），在第i天第二次买入股票
//dp[i][3] = dp[i-1][2] – prices[i]
//2.i-1天内都持有股票，在第i天什么都不做
//dp[i][3] = dp[i-1][3]
//所以dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] – prices[i]);
//dp[i][4]表示第i天第二次卖出股票的总金额
//dp[i][4]状态由以下两个状态得到
//1.i-1天内都持有股票（并且进行过一次买卖了），在第i天第二次卖出股票
//dp[i][4] = dp[i-1][3] + prices[i]
//2.i-1天内某一天卖出了股票，第i天什么都不做
//dp[i][4] = dp[i-1][4]
//所以dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i])
//初始化
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
//遍历顺序
for(int i = 1; i < prices.length; i++){
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] – 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[prices.length-1][4];
188.买卖股票的最佳时机IV
至多完成k笔交易，即至多可以k次买卖
在买卖股票III中至多可以2次买卖股票，一天的状态有5 = 2 * 2 + 1种
所以在该题中一天的状态有2 * k + 1种，从0到2*k一共2*k+1种
dp[i][j]表示第i天处于状态j时，最大金额为dp[i][j]
递推公式
j为奇数状态dp[i][1] = Math.max(dp[i-1][0] – prices[i], dp[i-1][1]);
j为偶数状态dp[i][2] = Math.max(dp[i-1][1] + prices[i], dp[i-1][2]);
初始化
偶数状态都初始化为0，奇数状态都初始化为-prices[i]
for(int j = 0; j < 2 * k; j += 2){//偶数状态都初始化为0，奇数状态都初始化为-prices[i]
dp[0][j+1] = -prices[0];
}
//遍历顺序
for(int i = 1; i < prices.length; i++){
for(int j = 0; j < 2 * k – 1; j += 2){
dp[i][j+1] = Math.max(dp[i-1][j] – prices[i], dp[i-1][j+1]);
dp[i][j+2] = Math.max(dp[i-1][j+1] + prices[i], dp[i-1][j+2]);
}
}
37.买卖股票的最佳时机含冷冻期
本题在最佳买卖股票II中加入了冷冻期概念，都是无限交易次数
状态0：dp[i][0]表示第i天持有股的金额
//下面三个状态就是不持有股票的状态
状态1：dp[i][1]表示前i天中的某一天卖完股票后，一直到第i天为止保持什么都不做的状态
状态2：dp[i][2]表示第i天卖出股票的状态
状态3：dp[i][3]表示第i天处于冷冻期的状态
dp[i][0]的状态获取分析：
1.前i-1天保持卖完股票后什么都不做的状态，在第i天买入股票
dp[i][0] = dp[i-1][1] – prices[i];
2.第i-1天处于冷冻期，在第i天买入股票
dp[i][0] = dp[i-1][3] – prices[i];
3.前i-1天一直持有股票
dp[i][0] = dp[i-1][0];
dp[i][1]的状态获取分析：
1.前i-1天也是保持卖完股票后什么都不做的状态
d[i][1] = dp[i-1][1];
2.在第i-1天处于冷冻期
dp[i][1] = dp[i-1][3];
dp[i][2]的状态获取分析：
前i-1天内一直持有股票，在第i天卖出
dp[i][2] = dp[i-1][0] + prices[i];
dp[i][3]的状态获取分析：
第i-1天卖出股票
dp[i][3] = dp[i-1][2];
//初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
//遍历数组
for(int i = 1; i < prices.length; i++){
dp[i][0] = Math.max(Math.max(dp[i-1][1] – prices[i], dp[i-1][3] – prices[i]), dp[i-1][0]);
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(Math.max(dp[prices.length – 1][1], dp[prices.length – 1][2]), dp[prices.length – 1][3]);
714.买卖股票的最佳时机含手续费
本题在最佳买卖股票II中加入了手续费概念，都是无限交易次数
只要把卖出股票的时候减去手续费就行了，其它不变
public int maxProfit(int[] prices, int fee) {
//无限次买卖
//每卖出股票金额就减去2
//dp[i][0]表示持有股票 ,dp[i][1]表示不持有股票
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i-1][1] – prices[i], dp[i-1][0]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i] – fee);
}
return dp[prices.length – 1][1];
}
子序列问题：
300.最长递增子序列
1.dp[i]表示以nums[i]为结尾的最长递增子序列的长度为dp[i]；
2.递推公式：
dp[i]的状态可以由在nums[i]之前的元素j为结尾的最长递增子序列的长度dp[j]推出
0 < j < i，去遍历nums[j]，将其与nums[i]做判断
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
3.初始化
由dp[i]定义可得，不管以哪个元素为结尾，此时最长递增子序列的长度初始化都为1
dp[i]=1；
4.遍历顺序
for(int i = 1; i < nums.length; i++){
for(int j = 0; j < i; j++){
//递推公式 if(nums[j] < nums[i]){
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
//得到最大值
result = Math.math(result, dp[i]);
}
}
5.返回结果
由dp[i]定义可得，为得到最长递增子序列的长度，我们需要遍历整个dp[i]，找出最大的那个dp[i]，就是最长递增子序列的长度。
674.最长连续递增子序列
与最长递增子序列这道题基本一样，因为子序列要求连续，所以只需要比较nums[i-1]与nums[i]大小即可，就不用内套for循环遍历j了
718.最长重复子数组
此题的子数组就是指连续子序列
1.dp[i][j]表示以numsA[i-1]为结尾的numsA数组，和以numsB[j-1]为结尾的numsB数组，两者的最长重复子数组长度为dp[i][j]。
问：为什么不像前两道题一样表示以numsA[i]为结尾和以numsB[j]为结尾呢？
答：如果像这样设置，那么就导致初始化的时候dp[0][j]和dp[i][0]就有了意义，
比如说dp[0][j]，表示数组A的numsA[0]元素要和numsB[j]的所有元素遍历一遍，确定哪个相等然后赋值为1，不相等在赋值为0。代码显得很冗余。
而表示以numsA[i-1]为结尾和以numsB[j-1]为结尾，就可以使得初始化的时候dp[0][j]和dp[i][0]变得没有意义，单纯为了递推状态而设计，所以初始化为0就可以了。
int[][] dp = new int[numsA.length + 1][nums.length + 1];
2.递推公式，在比较完数组A的numsA[i-1]和数组B的numsB[j-1]之后，比较下一个元素时，需要将两个数组同时回退，所以dp[i][j]的状态是由dp[i-1][j-1]得到的
所以递推公式为：
if(numsA[i-1] == numsB[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
3.初始化
因为我们定义的dp[i][j]，表示的numsA[i-1]和numsB[j-1]，所以对于dp[0][j]和dp[i][0]必须初始化为0，否则没意义。
4.遍历顺序
for(int i = 1; i <= numsA.length; i++){
for(int j = 1; j <= numsB.length; j++){
//递推公式
if(numsA[i-1] == numsB[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
//这里直接取最大值，减少后续为了得到结果还要遍历dp数组的冗余操作
result = Math.max(result, dp[i][j]);
}
}
1143.最长公共子序列
1.dp[i][j]表示长度为[0, i-1]的字符串text1 与 长度为[0, j-1]的字符串text2 的最长公共子序列长度为dp[i][j]
为什么设置为[0, i-1]和[0, j-1]，而不是[0, i]和[0, j]，在最长重复子数组中解释了，就是因为初始化更简单
int[][] dp = new int[text1.length() + 1][text2.length() + 1];
2.递推公式
dp[i][j]的状态可以从三个方向推出
(1)dp[i-1][j-1]
if(text1[i-1] == text2[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
}
(2)dp[i-1][j]
(3)dp[i][j-1]
第(2)种和第(3)种状态取最大值赋给dp[i][j]
详解：我们在比较完text1[i-1]与text2[j-1]时，发现两者不同，那么我们就要比较[0, i-2]的ab字符串与[0,j-1]的abe字符串的最长重复子序列（因为是子序列，不是子数组，所以不要求连续），以及比较[0, i-1]的abc字符串与[0,j-2]的ab字符串的最长重复子序列
else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
3.初始化
dp[i][0]=0;
dp[0][j]=0;
4.遍历顺序
for(int i = 1; i <= text1CharArray.length; i++){
for(int j = 1; j <= text2CharArray.length; j++){
//递推公式
}
}
5.打印
返回结果，因为要返回最长公共子序列，所以肯定在dp数组的最后一个元素
return dp[text1.length()][text2.length()];
1035.不相交的线
思路：与求最长公共子序列是一模一样的题。
直线不能相交，这就是说明在字符串nums1中找到一个与字符串nums2相同的子序列，且这个子序列
不能改变相对顺序，只要相对顺序不改变，连接相同数字的直线就不会相交。
本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！
53.最大子序和
思路：
1.dp[i]表示以nums[i]为结尾的最大连续子序列和为dp[i]
int[] dp = new int[nums.length];
2.递推公式
dp[i]的状态可以由以下两种情况得到：
情况1：dp[i-1] + nums[i]，在前面dp[i-1]基础上，再加上nums[i]；
情况2：nums[i]，舍弃前面的序列和，从nums[i]开始重新计算。
所以递推公式为：
dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
3.初始化
dp[0] = nums[0];
4.遍历顺序
5.返回dp的最大值
392.判断子序列
1.dp[i][j]表示长度为[0, i-1]的字符串s 和 长度为[0,j-1]的字符串t ，两者的最长公共子序列的长度为dp[i][j]
然后判断dp[s.length()][t.length()] ?= s.length();
如果相等就返回true；如果不相等就返回false。
整体上与那道最长公共子序列的题目解法一模一样
2.递推公式
dp[i][j]从三个方向获得
3.初始化，全初始为0
4.遍历顺序
5.打印
115.不同的子序列
题目解析：
计算在s的子序列中t出现的次数，就是s如何删除元素可以得到t。
1.dp[i][j]表示长度为[0,i-1]的字符数组 s 中 有 以长度为[0, j-1]的字符数组 t 的个数为dp[i][j]。
2.递推公式
当s[i-1] == t[j-1]时情况如何：
dp[i][j]可以由两种情况得到：
一部分是用s[i-1]来匹配，那么个数是dp[i-1][j-1]。即不考虑当前s字串和t字串的最后一位字母
一部分是不用s[i-1]来匹配，那么个数是dp[i-1][j]
所以dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
当s[i-1] != t[j-1]时情况如何：
dp[i][j] = dp[i-1][j];
3.初始化
dp[i][0]表示长度为[0, i-1]的字符串s 有多少 长度为-1的字符串t(即空字符串)，换句话来说就是s与多少种删除方法得到空字符串t。所以dp[i][0] = 1；
dp[0][j]表示长度为-1的字符串s 有多少长度为[0, j-1]的字符串t，所以初始化为0，dp[0][j] = 0;
dp[i][0]和dp[0][j]的交集dp[0][0] = 1;
4.遍历顺序
5.打印
返回return dp[s.length()][t.length()];
583.两个字符串的删除操作
1.dp[i][j]表示长度为[0, i-1]的字符串word1和长度为[0, j-1]的字符串word2，想要让两者相等，所需要删除元素的最少次数为dp[i][j]
2.递推公式
两个字符串比对之后两种情况：
情况1：word1[i-1] == word2[j-1] 不需要删元素
dp[i][j] = dp[i-1][j-1];
情况2：word1[i-1] != word2[j-1] 需要删元素
需要删元素时又分为三种情况
情况1：删除word1[i-1]元素
dp[i][j] = dp[i-1][j] + 1;
情况2：删除word2[j-1]元素
dp[i][j] = dp[i][j-1] + 1;
情况3：同时删除word1[i-1]元素和word2[j-1]元素
dp[i][j] = dp[i-1][j-1] + 2;
因为dp表示删除元素的最少次数，所以要取最小值
dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 2);
小细节：因为dp[i][j-1] + 1 = dp[i-1][j-1] + 2为什么会相等？
答：对于情况2来说，dp[i][j-1] = dp[i-1][j-1] + 1；dp[i][j-1]本来就不考虑word2[j-1]了，那么在此基础上不考虑word1[i-1]，就达到了删除两个元素的效果，然后等式两侧在加1，即dp[i][j-1] + 1 = dp[i-1][j-1] + 1；出现情况2和情况3等价的结果。
所以结果可简化为dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1);
3.初始化
dp[i][0]:表示长度为[0, i-1]的字符串word1与空字符串word2，想要让两者相等，需要删除i个元素
所以dp[i][0] == i;
dp[0][j]同理
dp[0][j] == j;
4.遍历顺序
正常遍历
5.打印
返回结果
72.编辑距离
1.dp[i][j]表示以i-1为结尾的word1 和 以 j-1为结尾的word2，想要让两者相等，最少需要操作数为dp[i][j]
2.递推公式
当word1[i-1] == word2[j-1]时
此时不需要任何操作，dp[i][j]可由前一个状态得到
dp[i][j] = dp[i-1][j-1];
当word1[i-1] != word2[j-1]时
分为三种情况：
删除
添加
替换
先看删除操作：
(1)只删除word1[i-1]，即不考虑word1[i-1]
dp[i][j] = dp[i-1][j] + 1；
(2)只删除word2[j-1]，即不考虑word2[j-1]
dp[i][j] = dp[i][j-1] + 1;
(3)删除word1[i-1]也删除word[j-1]
dp[i][j] = dp[i-1][j-1] + 2;
情况2和情况3等价
再看添加操作：
添加操作和删除操作是一样的效果
最后看替换操作：
替换操作下是word1[i-1]和word2[j-1]不相等，然后只改变一个就可以相等
所以dp[i][j] = dp[i-1][j-1] + 1;
综上，最终的dp[i][j] = 取最小值
3.初始化
dp[i][0] = i;
dp[0][j] = j;
4.遍历顺序
5.打印，返回结果
647.回文子串
1.dp[i][j]表示区间范围[i, j]（左闭右闭）的子串是否是回文串，如果是，那么dp[i][j]=true；如果不是，那么dp[i][j]=false。且j >= i。
boolean[][] dp = new boolean[s.length()][s.length()];
2.确定递推公式
整体上分两种情况
当s[i] == s[j]时
又分三种情况
情况一：下标i和下标j相同，即只有一个字符例如a，当然是回文串，dp[i][j] = true;
情况二：下标i和下标j相差为1，例如aa，也是回文串，dp[i][j] = true;
情况三：下标i和下标j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，那么看i到j区间是不是回文子串就看aba是不是回文就行了，那么aba的区间就是 i+1 与 j-1 区间，这个区间是不是回文就看dp[i+1][j-1]是否为true。如果是true，那么dp[i][j] = true; 如果是false，那么dp[i][j] = false;
当s[i] != s[j]时
此时不是回文串，即dp[i][j] = false;
递推公式每次为true时，result++用于记录回文子串的个数。
3.初始化
dp[i][j] = false；
4.遍历顺序
从dp[i][j]定义与递推公式上可以看出，情况三中dp[i][j]状态是由dp[i+1][j-1]状态得到的，即dp[i+1][j-1]在dp[i][j]的左下角，所以要从下到上，从左到右的遍历
for(int i = s.length()-1; i >= 0; i–){
for(int j = i; j < s.length(); j++){
//递推公式
}
}
5.打印，返回结果return result；
516最长回文子序列
1.dp[i][j]表示区间范围[i, j]的字符串的最长回文子序列的长度是dp[i][j]
2.递推公式
分两种情况
s[i] == s[j]
此时dp[i][j] = dp[i+1][j-1] + 2;
s[i] != s[j]
排除s[i]，此时dp[i][j] = dp[i+1][j];
排除s[j]，此时dp[i][j] = dp[i][j-1];
所以dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
3.初始化
i==j的dp初始化为1
4.遍历方向
for(int i = s.length() – 1; i >= 0; i++){
for(int j = i + 1; j < s.length(); j++){
//递推公式
}
}
5.打印，返回结果return dp[0][s.length()-1];
2 Responses
支持一下！
博主太细啦