动态规划算法

动规五部曲

1. 确定dp数组和下标的含义
2. 写出递推公式
3. 确定dp数组如何初始化
4. 确定遍历顺序（方向）
5. 打印，举例推导验证dp数组是否正确

背包问题

01背包

• 可使用二维背包，一维滚动背包

二维背包

基本了解

• 基本递推公式 : dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])

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

• 遍历顺序一般是先物品，再背包。也可以先背包，再物品

• 第一列初始化为0，第一行为第一个物品能否装入的价值

• dp的方向是由左上方决定的，遍历顺序从前往后/从后往前都可以

一维背包/滚动背包

• 基本递推公式 : dp[j] = max(dp[j],dp[j - weight[i]] + value[i])
• 需要先遍历物品，再遍历背包，遍历背包时要倒序遍历
• 初始化为0
• dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

为什么背包容量循环需要倒序：

dp[j - weight[i]] + value[i] : 说明是从左边的值来寻找当前合适的值

如果倒序，此时j从大到小，从左边：左边初始化都为0，所以不会使用到已经用过的物品

如果顺序，此时j从小到大，从左边：假如已经填了第一个物品，那么第二次，查找左边，就会继续把第一个物品的值加上

题型类型

1.纯01背包，计算背包装满的最大价值

2.能否填满背包（一般背包容量也可以是指定数字，数组里的数作为元素，能否达到指定数字）

• 不同点：返回值是和需要的容量作比较后的布尔值

3.尽量填满背包

4.填满背包的方法数量

• 不同点 ：

  1.递推公式不同: 总填充方法 = 不要该物品的填充方法+空出该物品容量，要该物品的填充方法，以及分支条件，如果装不下该物品，采用之前的填充方法数

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

  2.初始化方式不同：第一行为第一个物品填满该容量的方法，第一列为1（空容量，不放物品有一种方法）

5.填二维背包（有两种重量）

• 不同点：

  1.递推公式不同，因为是二维背包，所以需要减去两个维度的重量:dp[i][j] = max(dp[i][j], dp[i-weight[x]][j-weight[y]]) 2.遍历背包容量时，从后向前遍历

多重背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

• 和01背包不同的是：此时内层for循环的顺序为从小到大，无需倒序
• 背包容量和物品的先后顺序决定是求组合数还是求排列数
• 先物品 后背包 : 组合数
• 先背包 后物品 ：排列数

完全背包

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

• 把每件物品看作一件，就是01背包问题

打家劫舍

子序列问题

常见题目类型

单序列的判断：

【最长递增子序列】

示例 1： 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

• 不要求是子数组，但要求子序列中的数严格递增

• dp的定义 ： i之前，包括i,以nums[i]为结尾的最长递增子序列的长度

• 递推公式 :

  • 使用两层for循环，外层作为当前循环到的元素nums[i],内层作为其之前的数nums[j]

  • 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值

  • 判断是否当前nums[i] > nums[j]

  • dp[i] = max(dp[i] + 1 , dp[i])

• 初始化：

  • 全都初始化为1，单个子序列

• 结果 ： 根据dp数组的定义，结果并不是在dp[length-1]中，而是要在循环里寻找以某个nums[i]为结尾的最大值

【最长连续递增子序列】

示例 1： 输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

• 与上一题相比，多了连续,说明要按照数组中的数字顺序严格递增

• 只需要判断当前nums[i]的前一个数nums[i-1],无需再遍历之前所有数

• dp的定义和上一题相同

• 递推公式：

  • 只需要判断if(nums[i] > nums[i - 1]),无需第二层循环

【最大子数组和】

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

• 和 【最长递增子序列】 类似， 不需要连续，但是求最大的和，而不是最长有多少个

• dp定义也差不多相同 ：以下标i(nums[i])为结尾的最大连续子序列和为dp[i]

• 递推公式

  • 不需要判断
  • dp[i] = max(dp[i - 1] + nums[i] , dp[i])
  • 有可能当前的比之前的大，所以要取最大值

• 同理，最后的结果不再最后一个dp[length-1]中

双序列的判断

【最长重复子数组】

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1： 输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3,2,1] 。

• ==dp数组的定义 ： 以i-1为结尾的nums1[i-1] 和 以 j-1 为结尾的nums2[j-1] 的最长重复子数组为dp[i][j]==
• ==为什么要定义为i-1,j-1而不是i,j : 省去了初始化时的麻烦，直接初始化为0就可以了==

如果定义 dp[i][j]为 以下标i为结尾的A，和以下标j 为结尾的B，那么 第一行和第一列毕竟要进行初始化，如果nums1[i] 与 nums2[0] 相同的话，对应的 dp[i][0]就要初始为1， 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话，同理。

• 需要判断的是两数组当前以i-1,j-1为结尾时的子数组是否相同，相同说明此时是重复数组
• 递推公式 ：

  • for循环 ： 两次，从1开始，结束条件为<=length, 是根据dp数组的定义决定的

  • 判断条件 : nums1[i-1] == nums[j-1]

  • dp[i][j] = dp[i-1][j-1] + 1

• 注意最后的结果不在dp[length][length] 而是在循环中某处得到的最大值

【最长公共子序列】

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。 两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace” 输出：3
解释：最长公共子序列是 “ace” ，它的长度为 3 。

• 和 【最长递增子序列 】 类似， 不过是两个数组。

• 不要求是公共子序列（不严格递增）

• dp数组的定义:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]

• 递推公式 ：

  • 需要在上一题的基础上加上进一步判断如果当时两个数不相同的条件
  • 如果相同， 和上一道题相同 dp[i][j] = dp[i-1][j-1] + 1
  • 如果不相同，在两个数组之前拿到的最大值中取最大的一个 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

• 注意此时是从[0 - i]的最大值，所以本题的最大值就在dp[length][length]里

【不相交的线】

在两条独立的水平线上按给定的顺序写下 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 的直线相交。

• 其实就是求最长公共子序列

【判断子序列】

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，“ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = “abc”, t = “ahbgdc” 输出：true

• 和 【最长公共子序列】 类似，不过本题只需要删除t，s不动
• dp数组的定义和 【最长公共子序列】 相同
• 递推公式：
  • 此时的else分支条件发生变化:
    • 原是 ： dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    • 此时 ： dp[i][j] = dp[i-1][j] (i作为代表t的数组时)
    • 解释 ： 如果此时两字符串的最后一个字符不相同，那么就需要减去t当前的字符，把dp[t-1]中的内容作为最大值。而s不能变。
• 结果 ： 判断最后结果是否等于s字符串的长度

【不同的子序列】

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1：

输入：s = “rabbbit”, t = “rabbit” 输出：3 解释： 如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。 rabbbit rabbbit rabbbit

• 和 【判断子序列】 , 【最长公共子序列】 类似 , 不过改成了求出现的个数，而不是最长有多长

• dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

• 递推公式

if(s[i-1] == t[j-1]):
    dp[i][j] = dp[i-1][j-1]+dp[i-1][j]
else:
    dp[i][j] = dp[i-1][j]

• 不同点 : 不是判断是否为子序列(不求最大值)，也不是求最长公共子序列(不求严格顺序最大值), 而是求有几个，所以需要当相等时，用当前dp+之前dp,不等时，相当于最大值为之前的dp。

• 初始化: 根据递推公式可得，此时要对根据dp的定义数组进行初始化(dp[i][0],dp[0][j])。

  • dp[i][0]: 以i-1为结尾的s可以随便删除元素，出现空字符串的个数。:当i=1，应该有一个空字符串，所以应都初始化为1
  • dp[0][j]: 空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数,0
  • dp[0][0]：应该是1，空字符串s，可以删除0个元素，变成空字符串t。

【两个字符串的删除操作】

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。

每步 可以删除任意一个字符串中的一个字符。

示例 1：

输入: word1 = “sea”, word2 = “eat” 输出: 2 解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat “变为 “ea”

• dp数组的定义： 以i-1为结尾的word1 和 j-1为结尾的word2 ， 想要达到相等，需要删除元素的最小次数

• 递推公式 ： 分为此时 i-1 == j-1 , i-1 != j-1 两种。如果相等，说明不需要删除，保持上一次的操作次数，如果不相等，就有 ： 删除word1中的字符，删除word2中的字符，同时删除两个中的字符三种情况，在这三种情况中取最小值。

if(sword1[i-1] == word2[j-1]):
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = math.max(dp[i-1][j] + 1, math.max(dp[i][j-1] + 1, dp[i-1][j-1] + 2))

【编辑距离】

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符

删除一个字符

替换一个字符

示例 1：

输入：word1 = “horse”, word2 = “ros”

输出：3

• dp数组的定义 ： 和上一道一样
• 需要注意的是，如何通过dp数组实现这三种操作？
• 对于插入/删除 ： 其实删除一个word1中的字符和word2中插入一个字符操作一样
  • 例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样
• 对于替换操作 ： 相当于在之前的dp[i-1][j-1]的基础上+1
• 递推公式:

if(word1.charAt(i-1) == word2.charAt(j-1)) {
					dp[i][j] = dp[i-1][j-1]; //如果相同，不操作
				}else {
					//如果不相同，在word1，word2，两个字符都删除的操作中选择操作数最小的
					dp[i][j] = Math.min(dp[i-1][j] + 1, Math.min(dp[i][j-1] + 1, dp[i-1][j-1]+2));
				}

【回文子串】

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：“abc” 输出：3 解释：三个回文子串: “a”, “b”, “c”

• dp数组的定义 ： 和之前求什么定义什么不同，此时要从回文串的性质来推导 ：
  • 左边字符记作i,右边字符记作j,两字符相同时，此时有三种情况：
    • 1.i,j指向同一个字符 ： 此时是回文子串
    • 2.i,j相隔一个字符: 此时也是回文子串
    • 3.i,j之间的距离 > 1 : 那么就要看 i-1, j-1对应区间的子串是否为回文字符，如果是，那么此时也是回文子串
• dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

	if(s.charAt(i) == s.charAt(j)) {
				
    	if(j - i <= 1) {
    		dp[i][j] = true;
    		result++;
    	}else {
        						
        		if(dp[i+1][j-1] == true) {
        			dp[i][j] = true;
        			result++;
        			}
        						
        		}
	}
			

• 遍历顺序 ： 根据递推公式确定，因为当前dp[i][j]是由dp[i+1][j-1]推导得出的，也就是由左下方推导出的，所以遍历顺序应当从下到上，从左到右进行遍历

• 初始化：默认都为false，避免出错

【最长回文子序列】

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

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

• 和上一题【回文子串】类似，不过由求回文子串变成了求回文子序列，两者最大的区别是子串要求连续，子序列不要求连续

• dp[i][j]： i~j之间范围内最长的回文子序列

• 递推公式：

  • 此时，如果i,j相同，那么就相当于在之前的回文子序列范围上+2个字符作为最长回文子序列

  • 如果i,j不相同，那么就从只取i,或者只取j的情况下选出最大值作为此时的最长子序列

				//如果i 和 j相等，从原来的最长子序列上加两个字符
				if(s.charAt(i) == s.charAt(j)) {
					dp[i][j] = dp[i+1][j-1] + 2;
				}else {
					//如果不相等，就从取i，取j，两个字符串里取最大值
					dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
					
				}

• 遍历顺序 ： 根据递推公式，可以知道还是从左下，左，下，三个方向递推当前结果，所以要从下往上，从左往右进行初始化

• 数组初始化：如果此时i == j,说明此时是回文子序列，长度为1。

//初始化当i = j时的情况为1（一个字符）
		for(int i = 0 ; i < s.length() ; i++) {
			dp[i][i] = 1;
		}

• 返回的结果 ： 根据dp的定义，应当返回:dp[0][s.length()-1],范围最大时的回文子串。