动态规划

1. 动态规划

感谢代码随想录

解题思路

1. 确定dp数组及其下标的含义
2. 确定dp数组
3. 确定如何初始化 ，和dp数组的遍历顺序
4. 举例推导dp数组

验证dp数组的Bug时

1. 打印程序日志
2. 自行推导dp数组
3. 检查dp数组与程序中哪里出现错误，对错误地方重点检查

1.1. 斐波拉契数列

1. dp是数列的值
2. dp[i] = dp[i-1]+ dp[i-2];
3. 初始化0，1即可
4. 注意：题目中要求计算n的值，对应f(n)的值，不是n-1

1.2. 跳台阶最省力方法

1. dp[i] 是第i层台阶使用的力气，dp需要从dp[i-1] 与 dp[i-2]之间选择体力最小的值
2. 题目中，从第0，1阶开始跳，初始值可以为0；
3. 从前向后遍历

1.3. 路径问题

1.3.1. 深度搜索

1.3.2. dp算法

1. dp[i][j]是到达i,j 的所有方法

2. 因为只能i, j只能左边dp[i-1][j]和上面dp[i][j-1]共同决定，所以dp由两数之和决定

3. 第一行和第一列只能由一种方法到达，初始化为1；

4. 从前向后遍历

5. 因为dp是由上方和左边+1组成，可以使用一维累加数组完成dp数组的效果

1.3.3. 使用图论

移动需要走M+n-2中方法，且其中需要走m-1中向下的步数，结果为$C_{m+n-2}^{m-1}$

由于阶乘数字较大，先求分子分母阶乘会超过long long 类型，所以边计算分子边计算分母

1. 如果能够整除分母，且分母没有除完，选择除以分母
2. 并且分子分母相加相减方向相同，尽快除以分母

int high = m-1;
int low = m+n-2;

int denominator = high;
long long numerator = 1;

// 求分母
for(int i = 1 ; i<= high ;i++) {
    numerator*= low;
    while(denominator>0 && numerator%denominator==0){
        numerator/= denominator;
        denominator--;
    }
    low--;
}
return numerator;

1.4. 有障碍的路径规划

1. dp[i][j]表示i, j 位置的路径选择方法， 所以当有障碍物时，无法到达这里，此时dp[i][j]=0,其余位置照常计算

牢牢记住dp的定义，如有异常情况，将dp值写出

1.5. 整数拆分

整数从i 拆分后分为i, n-i;

最大值取值有两个选择：

1. $i*( n-i )$，不进行下一轮的划分
2. $ i* 对(n-i)划分后的最大乘积$，因为i会从0-i 都会分割一次，所以只用对(n-i）进行划分，因为在遍历过程中都会遍历到
3. 其中2中的第二部分为问题1的子集，使用dp求解

dp[i] = max(dp[i],max(i*j, j*dp(i-j)))

因为dp[i] 被计算多次，最后需选择最大值，所以对dp[i]求最大值

1.6. 二叉搜索树数量

1. n个数组成二叉搜索树，以j为中间节点1....j ....n

   j左边有j-1-1+1= j -1个数字，构成二叉搜索树，数量为dp[j-1]
   j右边有n - j-1+1 =n-j个数字,构成二叉搜索树，数量为dp[n-j]

2. 左右子树为树的子问题, dp[i] += dp[j-1]*dp[i-j]

3. 初始化dp[0] =1;

4. 遍历顺序为从前向后，遍历

2. 背包问题

2.1. 0-1背包

1. 每种物品只能选择一个

dp[物品i][重量w] 表示当前 物品i 与前面的物品[0-(i-1)] 在重量为w情况下的最大价值

dp，当重量j足够放下物品i 计算途径有两种

1. 放入，总重量为j - w[i] 时的最大价值，加上 物品i 的价值v
2. 不放入，总重量为上一个物品i-1在重量j情况下选择结果的最大值

dp[i][j]从以上选择最大结果， dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]])+value[i]

2. 初始化，对于第一个放入物品情况初始化
3. 遍历，从前向后遍历，重量可以等于总重量

2.2. 数组分为两个相同的数组

1. 数组分的数组和界限为sum/2，等价为背包所能装的总的质量
   1. 每一个数字 = 放入的物品，放入进去相当于有了重量
   2. 放入进去后，物品的总价值累加，等于sum/2 时，背包正好被放满

2.3. 压石机

使最后一块石头重量最小

两两组合使得质量最小 = 将石头分为两堆， 第一堆减去第二堆尽可能小 = 两石堆的质量差距相同

回到问题2中

现在将二维dp数组使用一维滚动数组代替

1. 先遍历物品，再遍历质量，因为dp[0-i]之前的数据是上一轮迭代结果，dp[i]需使用之前的数据，所有从后先前迭代
2. 先遍历质量，再遍历物品，遍历得到当前质量j 下放下物品的最大价值，需计算出之前的数据，才能计算下一个质量下的最优值，所以必须从后向前迭代

第二种遍历方式错误，会造成物品选择两次

2.4. 目标和

目标和

1. 将目标和转换为 数据求和等于某个值n
2. 相当于将数值放入其中，可以得到值n

和为x, 差的和为sum -x ,所以 x- sum+x = target ，求出x = (target+sum)/ 2， 所以目标和为 (target+sum)/ 2

1. dp[i][j]是目标和为j 时选择i ，有多少组合方法

2. dp的组合方式

   1. 选择i ， 则方法总数为上一个数字总和为j - num[i], 即·dp[i-1][j-nums[i]]
   2. 不选择i，则方法总数为上一数字总和为j ,即dp[i-1][j]

   总方法= 1+2

3. 初始化：

   1. 对于第一个数字，只有一种j 有一种方法，其余方法数为0；
   2. 对于剩余数字，当j = 0时，总数为0数字的2*n;

2.5. 0-1字串

0-1

一个字符串strs= ["10", "0001", "111001", "1", "0"],求出有m个0， n个1的最大子集元素个数

此时题目相当于m,n相当于背包的重量，总重量小于m、n两个维度，字符串相当于物品，字符串0、1个数相当于每个物品的质量。

此时可以使用0-1背包

推荐使用滚动数组解决0-1背包问题

1. 初始化时将初始值置为0
2. 优先物品遍历，质量遍历时使用倒序遍历

3. 完全背包问题

1. 背包物品数量有无穷多个，可以重复选择

2. dp[i][j]公式含义： 第i个物品，在重量j条件下物品的最大价值

3. dp[i][j]计算方式

   1. 选择i, 预留重量j- weight[i]， 且背包中仍有i（区别0-1背包）， dp[i][j- weight[i]]
   2. 不选择i, 不预留质量，不选择i,背包中只有i-1物品的最大值， dp[i-1][j]

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

4. 初始化

   1. 对i = 0 初始化
   2. 对j = 0 初始化

3.1. 零钱兑换

此时求得是总的组合数，不是最大价值，dp[i][j] 是由i 是否选择两种情况组合的和

1. dp[i][j] = dp[i][j- weight[i]] + dp[i-1][j]
2. 初始化
   1. 第一行初始化，如果可以整除，则有组合方式，初始化为1
   2. 第一列初始化，重量>1 ,则重量=0时，只有一种组合方式，初始为1

< int < unsigned int < long long < unsigned long long

	int	unsigned int	long long	unsigned long long
	int32_t	uint32_t	int64_t	uint64_t
范围	2,147,483,647	4,294,967,295	9,223,372,036,854,775,807	18,446,744,073,709,551,615
十进制	2e9	4e10	9.2e18	1.8e19

3.1.1. 使用一维dp数组

1. 使用滚动数组 dp[j] = dp[j] + dp[j- weight[i]]
   1. 不选择时nochoose = dp[j]
   2. 选择时 choose = dp[j-weight[i]]
2. 初始化
   1. dp[0] 只有一种组合方式，初始化为1
3. 遍历顺序
   1. 先遍历物品，在遍历质量，是组合
      1. 且遍历质量时，需顺序遍历，此时可以放置多个同一物品，需使用到之前的数据，
   2. 先遍历质量，再遍历物品，是排列数量

先遍历物品，再遍历质量	先遍历质量，再遍历物品
先放物品i ，再放入物品i+1，有放入顺序，排除顺序不同的情况，计算的是组合数	先计算出当前质量下所有物品的最大值，表示质量j所有组合情况，没有顺序问题，是排列数

3.2. 求出排列数量

求出排列数量有两种思路

1. 完全背包的排列问题：

   1. 先遍历质量，再遍历物品， 可以得到排列数量

   2. 爬楼梯

   3. 爬到第i 层的值，等于之前能够爬到i的所有选择之和

      $ dp[i] = {dp[i- 能到i的跳跃次数]} 总和$

   4. 题目中用于跳跃到n的次数= 数组中用于相加等于n 的所有元素

3.3. 爬楼梯 = 完全背包排列问题

爬n阶台阶，每次能爬m 阶，两种思路解决

1. n阶台阶 = 背包总容量，m阶台阶是每次选择的物品质量，价值 = 重量 = j。dp[j]是装满j层的方法总数

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

   完全背包问题，优先遍历质量，再遍历物品

2. 爬到i 层是之前i-m 层所有爬楼方法的总和,

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

3.4. 零钱兑换的最小方法数

零钱兑换

1. dp[j] 兑换j所需的金币数量
2. dp[j] 由其 dp[i- coins[i]]兑换到当前值 的最小方法决定
   1. dp[j] = min(dp[j], dp[j- coins[i]])
3. 初始化，需比较最小值，需将dp[j] 初始化为UINT64_MAX
   1. dp[0] 方法数为0，初始化为0
4. 此时不是求总的组合数 / 排列数，任意顺序遍历均可

3.5. 完全平方数

完全平方数

1. dp与上一相同

3.6. 字串拆分

i 是需要达到的楼梯，

0-(i-1)是能够到达i之前所有的楼梯，对这些元素遍历，并检查 j - i 之间能否跳到i

dp[i] = dp[j] && (i-j)能否到达

切分(i-j) ，切记i.j均是加1 后的结果， 那么j = j'+1，起始位置为j'+1 ,即为j, 总长度为i' - j+1= i -1-j+1 = i-j

切分范围为(j, i-j)

3.6.1. 回溯遍历，使用数组保存状态

使用memory保存状态，之后可以直接使用

4. 多重背包问题

多重背包问题 = 物品展开的0-1背包问题

重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

相当于先遍历物品，再遍历物品的个数，再遍历背包(遍历物品个数在内部也一样)

物品i ， 质量为j, 最大数量为k

dp[i][j] 对于总重量j有两种计算方式

1. 不装： dp[i-1][j]
2. 装k个：dp[i-1][j-k*weight[i]] + k*value[i]
3. 初始化：
   1. j = 0 一列全部为0
   2. i =

初始化，与取值都是错误的，二维数组很复杂

建议使用滚动数组

物品i ， 质量为j, 最大数量为k

dp[j] 是物品i对于总重量j有两种计算方式

1. 不装： dp[j]
2. 装k个：dp[j-k*weight[i]] + k*value[i]

如果先遍历物品再遍历质量时，此时每次放入一个，不再需要乘上系数k

5. 打家劫舍问题

1. dp[i] 是第i 家可以打劫到的最大金额

2. dp[i]可以选择偷 / 不偷

3. 偷的话，需要偷i-2之前房屋的金额，加上第i家的前

   dp[i-2]+ nums[i]

4. 不偷的话，第i-1家可以被偷，所以第i的情况 = 第i-1家是否被偷的情况

   dp[i] = dp[i-1]

dp[i] = max(d[i-2]+ nums[i], dp[i-1])

3. 初始化，需要初始化第0，1 家

   1. dp[0] = nums[0], dp[1] = max(dp[0] , dp[1]);

4. 遍历顺序，从前向后

5.1. 成环的打家劫舍

成环

成环后，将首尾分开讨论

1. 不偷头，那么最后一间可以被偷

   

2. 不偷尾，那么第一间房间可以被偷

   

求两次的能偷的最大价值，比较，返回最大值

5.2. 二叉树的打家劫舍

树的后序遍历，统计孩子们偷钱，再由中间节点统计

1. 截至条件：
   1. 到NULL节点，偷的最大值为0
   2. 到叶子节点，偷的最大值是当前值
2. 处理逻辑
   1. 根节点偷
      1. 跳过左右孩子，计算从左右孙子偷到的金额
   2. 根节点不偷
      1. 计算左右孩子偷盗的金额
   3. 选择哪一个值更大，选择偷拿个
   4. 使用记忆化存储，使用map<root, val>,保存已访问节点的最大值，后续访问节点时，直接返回保存值

5.2.1. 树形的dp

dp[i] 取决于 i 的左右节点的dp[i->left], dp[i->right]

1. 截至条件，所以函数需要返回孩子节点的选择状态<不偷，偷>
   1. 到NULL节点，返回<0,0>
2. 处理逻辑：
   1. 当前节点偷，choose = val + 左右孩子不偷
   2. 当前节点不偷，可以考虑左右节点是否偷，nochoose = max(左孩子选择)+max(右孩子选择)

6. 股票问题

同一个i有两种状态， 状态之间互相推导

1. 第i天有两种状态， 持有股票 / 不持有股票， 分别设置为 dp[i][0]/ dp[i][1]

2. 第i天持有股票，可由两种方式推导

   1. 第i-1 持有股票

   2. 第i-1不持有股票，第i天购购入(因为之前没有购入股票，一切为0)

   3. dp[i][0] = max(dp[i-1][0], - price[i])

      如果之前卖出了股票，就成了由不持有股票状态dp[i-1][1]-price[i]

   第i天不持有股票，由两种方式推导

   1. 第i-1不持有股票

   2. 第i-1天持有股票， 第i购入股票

   3. dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i])

3. dp公式初始化，所有由第一天的状态组成，初始化

   1. 第一天持有股票dp[0][0] = -price[0]
   2. 第一天不持有股票 dp[0][1] = 0

4. 遍历顺序，从前向后遍历

6.1. 有限次购买股票

问题：dp数组由多种不同的状态，且不同状态之间互相推导

解决方法： 找出所有可能的状态，并推导不同状态之间的公式

最多有n次购买股票，可以设置五种状态

0	没有操作	dp[i][0]
1	第一次持有股票	dp[i][1]
2	第一次不持有股票	dp[i][2]
3	第二次持有股票	dp[i][3]
4	第二次不持有股票	dp[i][4]

1. 第一次持有股票

   1. 第i-1第一次持有股票

   2. 第i天没有操作状态购入股票

2. 第一次不持有股票

   1. 第i-1天不持有股票
   2. 第i-1天 持有股票后，第i天卖出股票

3. 第二次持有股票

   1. 第二次持有股票
   2. 第i-1天第一次不持有股票，第i天购入股票

4. 第二次不持有股票

   1. 第二次不持有股票
   2. 第i-1天持有股票， 第i天卖出股票

初始化：在第0天

1. 第一次购入股票， 为-price[0]
2. 第一次不持有股票，相当于第一天买了又卖了， 0
3. 第二次购入股票，相当于第一天买入又卖出，再买入， 为-price[0]
4. 略

dp结果： 只买一次股票包含在买两次股票结果中，所以第二次卖出股票为最终结果

6.2. 限制k次购买股票

k次购买

k次购买有2k中持有与不持有状态，+1中首次误操作状态

1. dp[i][j+1]次状态有 dp[i-1][j] ， 上一种状态dp[i-1][j]转换组成
   1. 由于奇数次状态为持有股票状态，需要购入股票，由上一状态 - price[i]得到
   2. 偶数次状态为不持有股票状态，卖出股票， 总的价格增加，由上一状态+ price[i]得到
2. dp[i][j]公式
   1. $dp[i]][j] = max(dp[i-1][j] , dp[i-1][j-1] + (-1)^j*prices[i])$
   2. 方便计算，可以将奇偶公式分开枚举

6.3. 含有冷冻期的股票购买

卖出股票后一天时冷冻期，冷冻期后时不持有股票状态

尝试描述购买股票过程中有多少种状态，画出其状态转化图， 有四种状态，

1. 持有股票状态 ， dp[i][1]
2. 不持有股票状态, dp[i][2]
3. 冷冻期, dp[i][3]
4. 当天卖出股票状态(此时状态与2不同) dp[i][4]

1. 当前持有股票，
   1. 可由前一天持有股票dp[i-1][1]得到，
   2. i-1 天不持有股票，买入股票得到， dp[i-1][2] - price[i]
   3. i-1冷冻期中后一天，买入股票， dp[i-1][3] - price[i]
2. 当前不持有股票
3. i-1是冷冻期， dp[i][3]
4. 当前是冷冻期
   1. i-1当天售出股票， dp[i-1][4]
5. 当天售出股票
   1. i持有股票，卖出， dp[i-1][1] + price[i]

初始化：

1. 持有股票时， 因买入股票， 初始为-price[0]
2. 其余状态不持有股票，初始不买不入，初始为0

遍历顺序：从前向后遍历

6.4. 含手续费的股票售出

卖出时缴纳手续费

1. 还是两种状态， 持有股票，不持有股票， 由持有股票售出股票-> 不持有股票，需缴纳手续费
2. dp转换公式
   1. dp[i][0] = max(dp[i-1][0] , dp[i-1][1] - price[i])
   2. dp[i][1] = max(dp[i-1][1], dp[i-1][0] + price[i] -fee) ，售出时缴纳手续费
3. 初始化： 略
4. 选择结果： 可以卖出，也可以不卖出，选择最大值情况

7. 子序列问题

字串问题操作数 = 不同结果的操作选择

1. 找到所有可能的操作
2. 当前情况可以由哪些操作得到，上一操作状态又是什么
3. 使用 max, min 选择最合适的操作

可以近似于 爬楼梯问题， 能爬到 num[i] 位置的最大长度

1. dp[i]表示为 i之前包括i内以nums[i]为结尾的序列， 单调增序列的最大长度,

2. for 0: j 中，能够爬到 if(nums[j] < nums[i]) 中， 长度最大值

if(nums[j] < nums[i] ) dp[i] = max(dp[i], dp[j] +1)

3. 初始化，所有序列初始为1

7.1. 最长连续子序列

子序列连续-递增

要求连续，所以只能从j-1跳到j的位置，所以只需要比较nums[j-1] < nums[j]， 不需要从[0,j-1]全部与nums[j]比较

7.2. 最长重复子序列

1. dp[i][j] 表示 以i-1 结尾的A数组 与 以j-1结尾的B 数组 最长公共子序列

   因为dp[i][j] 时比较了了i-1 与j-1的序列结果， 所以表示以i-1为结尾的子序列

2. if(A[i-1] == B[j-1]) dp[i][j] = max(dp[i-1][j-1]+1) , 比较的当前位置，因为i, j比实际i,j大1， 所以if中减去了1

3. 初始化 i=0 , j=0 各种情况都是错误，初始化为0

遍历顺序： dp[i][j]需要从1 开始遍历

7.2.1. 一维dp数组

1. dp[j]表示与j-1结尾的相同的最大长度

   因为是从上一个i-1复制下来得到，遍历过程中不能修改j-1的dp，否则影响后续计算

2. ·if(A[i-1] == B[j-1]) dp[j] = max(dp[j-1]+1)

3. 遍历顺序： i从头开始， j必须从后开始

7.3. 最长公共子序列

1. dp[i][j] 表示以i-1 结尾的序列与 以j-1为结尾的序列，最长的公共子序列
2. dp[i][j] 有两种计算方式
   1. A[i-1] == B[j-1] ，长度+1, dp[i-1][j-1]+1
   2. A[i-1] ！= B[j-1] ,需要看i-1和j / i 与j-1 是否有最长的公共子序列，从两者中选择最大值
3. 初始化：
   1. i=0, j=0情况，因为序号为0为空串， 与另一条序列的公共序列一定为0
4. 遍历顺序： 从前向后

7.4. 最大连续子序和

最大子序和

连续子序和，可以由上一个序列延续获得， 也可以上一序列中断， 由当前序列继续计算

1. dp[i] ，以i为结尾的最长子序和

2. dp[i] = max(dp[i-1]+ nums[i], nums[i])

3. 初始化，dp[0] 可以选择自身开始，或者从0开始

题目要求子序长度 >0 ，所以必须从自身开始

4. 遍历顺序： 从前向后遍历

7.5. 判断子序列

子序列a 对应 序列b 的子序列长度

dp[i][j]是子序列a与序列b相同子序列长度

1. 相同时 ， dp[i][j] = dp[i-1][j-1] + 1;

2. 不相同时，删除j节点，观察 dp[i][j-1]能到达的最大长度

   此时，只能删除j节点，删除i节点后，就不是原来的序列了

7.6. 不同的子序列

完整的序列t在s的子序列中出现的次数

1. dp[i][j], 以i-1结尾的序列t ，在以j-1为结尾的序列s中子序列出现次数

2. 有两种计算情况

   1. s[i-1] == t[j-1] ，看i-1, j-1 时匹配的结果， 同时还可以删除i-1看匹配结果(i-1可能由重复情况)

      相同情况时，选择用s[i] 与 t[j]比较，因为s[i]前一位可能等于后一位，所有也需要向前移动一位比较

   2. 不相同时，删除i-1看匹配结果，dp[i-1][j]

3. 初始化，i = 0 , j=0都是异常情况

   1. i =0 , s为空串， j与s相同结果为0
   2. j=0时，j是空串，s中删除到最后，一定有一串与j相同，初始化为1

4. 遍历顺序： 从前向后遍历

7.7. 删除操作

两个字串删除n次后，序列相同

7.7.1. 最长相同子序列长度

1. 求出两字串最长公共子序列，长度n；
2. 字串a,b删除除了公共子序列外的其他元素，删除后结果相同，删除长度 = 删除操作此处

7.7.2. 删除操作DP

1. dp[i][j]是以i-1为结尾的串a，以j-1为结尾的字串b需要删除的最小次数

2. dp[i][j]有两种情况，相同结尾，不同结尾

   1. a[i-1] == b[j-1]， 不需要删除操作，操作次数 = dp[i-1][j-1]

   2. a[i-1] ！= b[j-1]，需要删除 a,b的最后一个，或者两个都删除

   3. 删除i-1 , dp[i-1][j]+1

   4. 删除j-1, dp[i][j-1]+1

   5. 两个都删除， dp[i-1][j-1]+2

   使用max对三种方案进行选择， 3 包含在1， 2中，可以省略3

3. 初始化，i=0, j=0异常情况，需初始化

   1. i=0， 字串a = NULL, 字串b[j] 需删除 j次
   2. j = 0 ，同上

4. 遍历顺序： 从前向后

7.8. 编辑距离

字串编辑有三种操作，字串a[i], b[j], 最后一位不同

1. 删除，删除a 的最后一位a[i]，b没有改变

2. 增加，在b[j-1]后增加一位a[i]与a相同， 增加一位a[i]与删除一位a[i]的操作力度相同

3. 替换，

4. dp[i][j] 表示以i-1为结尾的串a，以j-1为结尾的字串b需要操作的最小次数

5. dp[i][j]有两种情况，相同结尾，不同结尾

   1. a[i-1] == b[j-1]， 不操作，记录之前的操作次数= dp[i-1][j-1]

   2. a[i-1] ！= b[j-1]， 进行以上三种操作

      1. 删除， dp[i-1][j]+1, dp[i][j-1]+1
      2. 增加， dp[i-1][j]+1, dp[i][j-1]+1
      3. 替换， dp[i-1][j-1]+1

      使用max对操作进行选择

6. 初始化，i= 0, j =0的情况，处理同上

7. 遍历顺序，从后向前遍历

8. 回文

8.1. 回文子串

8.1.1. DP算法

求回文字串的数量

1. dp[i][j]表示 [i,j]之间的字符是否为回文字串， 然后统计数组dp中有多少个 true,, = 有多个回文字串

2. 两种情况

   1. a[i] = a[j],
      1. [i, j]之间相同 / 相邻，一定是回文子串
      2. [i,j]之间不相邻，dp[i+1][j-1]是回文串，则true
   2. 不相同，不是回文串，跳过

3. 初始化

   1. dp[i][j]全初始化为false

4. 遍历顺序

   从左下角开始遍历， 即 下-> 上，左-> 右遍历

   

8.1.2. 双指针 中心扩散

回文串 由 中间1个 / 2个向左右扩散，统计扩散数量，不能扩散时，返回得到扩散的最大数量

1. 中间 1 个向左右 扩散
2. 中间 2 个向左右扩散
3. 相加得到结果

8.2. 最长回文子串

最长回文字串

字串要求 是连续的

8.3. 最长回文子序列

最长回文序列

回文序列可以不连续

1. dp[i][j] ，表示[i,j] 之间最大的回文序列长度

2. dp[i][j]两种情况

3. a[i] == a[j]，子序列长度加2 ， dp[i+1][j-1]+2

4. a[i] != a[j]，那就是前一个区间的最大长度，可以缩短i/ j ，max(dp[i-1][j], dp[i][j-1])

5. 初始化

   1. 由性质 i == j 时候， dp[i+1][j-1]+2

      因为i+1 > j-1无意义，所以i==j需要单独初始化

   2. 其余初始化为0

6. 遍历顺序： 下- > 上， 左-> 右

   遍历时， i == j时，已经初始化，且公式计算不到，所以j只需要从i+1开始遍历

   dp[i+1][j-1]+2,所以 `i <= s.size()-2, i >=0