6-刷题记录

动态规划

动态规划理论基础
1. 如果某一问题有很多重叠子问题，使用动态规划是有效的。
2. 区别于贪心，贪心没有状态推推导，是直接从局部里选最优的，而动态规划中每一个状态都是由上一个状态推导而来的。
3. 解决五部曲
  1. 确定dp数组以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组
4. debug-把dp数组打印出来，看看是不是按照自己的思路推导的
斐波那契数
1. 重点：方法论理解-五部曲应用
  1. 确定dp数组以及下标的含义–dp[i]的定义是，第i个数字的斐波那契数值是dp[i]
  2. 确定递推公式，状态转移方程–dp[i] = dp[i-1] + dp[i-2]
  3. dp数组如何初始化–dp[0] = 0;dp[1] = 1;
  4. 确定遍历顺序：dp[i]是依赖于前两个 i-1 和 i-2 ，从前向后遍历
  5. 举例推导dp数组：当n=4时，0,1,1,2
爬楼梯
1. 整体思路，第i阶楼梯，可以是从第i-1阶跨越1步而来，也可以是从第i-2阶跨越2步而来。
2. 五部曲应用
  1. 确定dp数组以及下标的含义：dp[i]是在第i阶有dp[i]种方法
  2. 确定递推公式：dp[i] = dp[i-1]+dp[i-2]
  3. dp数组如何初始化：dp[1] = 1,dp[2] = 2;
  4. 确定遍历顺序：从前向后遍历
  5. 举例推导dp数组：当n=4时，1,2,3,5
使用最小花费爬楼梯
1. 确定dp数组及下标的含义：dp[i]表示，到达第i阶台阶，需要花费的最少体力值
2. 确定递推公式：dp[i] = dp[i-1]+cost[i-1] 或者 dp[i] = dp[i-2]+cost[i-2],需要选择最小值
3. dp数组如何初始化：dp[0]=0,dp[1]=0。（题目中说：你可以选择下标为0或者下标为1的台阶开始爬楼梯，也就是说，到达第0或1个台阶是不需要耗费体力的）
4. 确定遍历顺序：从前到后遍历cost数组
5. 举例推导dp数组：如题目
不同路径
1. 确定dp数组以及下标的含义：dp [i] [j] 表示，在棋盘上ij的位置，有几种路径
2. 确定递推公式：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1];
3. dp数组如何初始化:dp[i] [0] = 1;dp[0] [j] = 1;尤其注意初始化，一直往右走和一直往下走都只有一条路径。
4. 确定遍历顺序：从左到右一层层遍历
5. 举例推导dp数组：如题目
不同路径II
1. 确定dp数组以及下标的含义：dp[i] [j] 表示在坐标位置为i，j时，一共有几种路径
2. 确定递推公式：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]
3. dp数组如何初始化：一直往右走或者一直往下走，都只有一条路径，需初始化为1，但是需注意，当这两条路出现障碍物时，剩下的位置（包括障碍物出现的位置）都会被初始化为0
4. 确定遍历顺序：从左向右，从前向后遍历，当遇到障碍物时，该位置的dp数组对应下标为0。
5. 举例推导dp数组：如题目
整数拆分
1. 确定dp数组以及下标的含义：dp[i] 表示拆分i，得到的最大乘积
2. 确定递推公式：易得dp[i]的来源可能有两个，dp[i] = i * (j-i)，或者dp[i] = j * dp[i-j]，需要选择两者中的最大值。
  1. 注意，dp[i]还要跟之前的dp[i]作比较，不能被覆盖
    1
    dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
3. dp数组如何初始化，根据dp数组的定义，可初始化dp[2] = 1;
4. 确定遍历顺序，从递推公式中可以看出，需要从前向后遍历
5. 举例推导dp数组：如题目
不同的二叉搜索树
1. 确定dp数组以及下标的含义：dp[i]代表从1……i的节点构成的二叉搜索树的个数
2. 确定递推公式：dp[i] += dp[j-1] * dp[i-j]
3. dp数组如何初始化：dp[0]=1
4. 确定遍历顺序：从前向后遍历
5. 举例推导dp数组：如题目
0-1背包理论基础（一）
1. 背包问题：有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
  1. 确定dp数组以及下标的含义：用dp[i] [j] ，使用二维数组，分别表示物品和背包的容量，dp[i] [j]表示从下标[0~i]的物品里任意选，放进容量为j的背包里，价值总和最大是多少。
  2. 确定递推公式：
    1. 对于一个位置，不放物品i，那么里面不放物品i的最大价值是dp[i-1] [j]
    2. 对于一个位置，背包空出物品i的容量后，背包容量为j-weight[i]，dp[i-1] [j-weight[i]]为背包容量为j-weight[i]且不放物品i的最大价值，那么dp[i-1] [j-weight[i]] +value[i]就是背包放物品i得到的最大价值
    3. 所以有:dp[i] [j] = max(dp[i-1] [j],dp[i-1] [j-weight[i]]+value[i])
  3. dp数组如何初始化
    1. dp[i] [0] = 0 且 dp[0] [j] 也需要初始化
  4. 确定遍历顺序：先遍历物品，再遍历背包
  5. 举例推导dp数组
0-1背包理论基础（二）滚动数组
1. 确定dp数组以及下标的含义：dp[j]表示当背包容量为j时，背包的最大价值总和为dp[j]
2. 确定递推公式：dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
3. dp数组如何初始化：dp[0] = 0
4. 确定遍历顺序：
  1. 后序遍历背包，为了保证物品i只被放入一次
  2. 先遍历物品嵌套遍历背包
5. 举例推导dp数组
分割等和子集
1. 思路转换：是否可以将这个数组分割成两个子集，使两个子集的元素和相等 -> 是否能在数组集合中找到 sum/2 的子集总和 –>能否把sum/2的背包装满。
  1. 0-1背包问题：物体的重量即为数组元素的大小，价值也为大小，物体的数量为数组的所有元素个数
2. 确定dp数组以及下标的含义：dp[j] 表示当背包容量（子集总和）为j时的背包的总价值
3. 确定递推公式：dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
4. dp数组如何初始化：dp[0] = 0;
5. 确定遍历顺序：先遍历物品，嵌套后序遍历背包
6. 举例推导dp数组：如题目
最后一块石头的重量II
1. 思路转换：尽量让石头分成重量相同的两堆，那么相撞之后剩下的石头就是最小的重量 -> 一堆石头的重量和是sum，所以我们的目的就是尽可能拼成 sum/2 的石头堆，那么剩下的那堆也是逼近sum/2的 -> 背包容量为sum/2，最多能装多少？
2. 确定dp数组以及下标的含义：dp[j]表示背包容量为 j 时能装进去的最大总价值（容量）是多少
3. 确定递推公式：dp[j] = max(dp[j] , dp[j-nums[i]]+nums[i])
4. dp数组如何初始化：dp[0] = 0;
5. 确定遍历顺序：还是先遍历石头，再嵌套后序遍历背包
6. 举例推导dp数组：如题目
目标和
1. 思路转换：结果为target，一定有left - right = target，并且left + right = sum，综合整理，可得 left = ( target + sum ) / 2 -> 问题转换为，要装满一个大小为left的背包，有几种方法？
2. dp二维数组
  1. 确定dp数组以及下标的含义：dp[i] [j]表示，当背包容量为j时，使用下标为i的nums[i]能够填满背包有dp[i] [j]种方法。
  2. 确定递推公式：dp[i] [j] = dp[i-1] [j] + dp[i-1] [j-nums[i]]
  3. dp如何初始化：由左上和上方推导而来，所以第一排和第一列需要初始化
    1. dp[0] [nums[0]] = 1，其余均为0
    2. dp[i] [0]=1，有例外，当物品数值就为0时，涉及到组合，截至有t个0，那么方法就为2^t
  4. 确定遍历顺序：从左到右，从上到下
  5. 具体推导dp数组：如题目
3. dp一维数组
  1. 确定dp数组以及下标的含义：dp[j]表示，当背包容量为j时，装满有几种方法？
  2. 确定递推公式：dp[j] = dp[j] + dp[j-nums[i]]
  3. dp如何初始化: dp[0] = 1
  4. 确定遍历顺序：同0-1背包问题滚动数组的遍历顺序
  5. 具体推导dp数组：如题目
一和零
1. 确定dp数组以及下标的含义：dp[i] [j] 表示最多有 i 个0和 j 个1的strs最大子集的个数。
2. 确定递推公式：由前一个str的字符组成推导而来，假设str中有zeroNum和oneNum
  1. 那么有dp[i] [j] = max(dp[i] [j]，dp[i-zeroNum] [j-oneNum] +1)
3. dp数组初始化：dp[0] [0] = 0;
4. 确定遍历顺序：遍历物品str，嵌套后序遍历背包
5. 具体推导dp数组：如题目
完全背包理论基础
1. 完全背包问题：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
  1. 确定dp数组以及下标的含义：dp[i] [j] 表示从下标0~i的物品里选择，每个物品可以选择无限次，放进容量为j的背包，价值总和最大是多少。
  2. 确定递推公式：
    1. 不放物品 i ：dp[i] [j] = dp[i-1] [j]
    2. 放物品 i ：dp[i] [j] = dp[i] [j-weight[i]]+value[i]
    3. dp[i] [j] = max(dp[i-1] [j] , dp[i] [j-weight[i]]+value[i])
  3. dp数组初始化：初始化dp[i] [0] = 0和dp[0] [j]
    1. 对于dp[0] [i]，在不超容量的情况下，可以一直装该物品
  4. 确定遍历顺序：可以先遍历物品再遍历背包，也可以先遍历背包再遍历物品
  5. 具体推导dp数组：如题目
零钱兑换II
1. 是一个完全背包问题，但是求解的是装满背包的最大组合数 –> 涉及到最后遍历顺序的问题
2. 二维dp
  1. 确定dp数组以及下标的含义：dp[i] [j] 表示凑成金额 j 的选用0~i的组合个数
  2. 确定递推公式：dp[i] [j] = dp[i-1] [j] +dp[i] [j-coin[i]]
  3. dp数组初始化：dp[i] [0] = 1; dp[0] [j]，如果coin[0]能够被 j 整除，那么就有一种方法，否则为0
  4. 确定遍历顺序：先遍历背包或者先遍历物品都可以
  5. 具体推导dp数组：如题目
3. 一维dp
  1. 确定dp数组以及下标的含义：dp[j] 表示凑成金额 j 的组合数
  2. 确定递推公式：dp[j] +=dp[j-coin[i]]
  3. dp数组初始化：dp[0] = 1;
  4. 确定遍历顺序：只能先遍历物品，再遍历背包。否则，先遍历背包，会有{1,4}，{4,1}两种相同的组合方式
  5. 具体推导dp数组：如题目
组合总和IV
1. 是一个完全背包问题，但是求解的是装满背包的组合的个数，但是此题注明，顺序不同的序列被视为不同的组合。
2. 确定dp数组以及下标的含义：dp[j] 表示凑成j 的组合数
3. 确定递推公式：dp[j] +=dp[j-nums[i]]
4. dp数组初始化：dp[0] = 1;
5. 确定遍历顺序：只能先遍历背包，再遍历物品
6. 具体推导dp数组：如题目

零钱兑换

1. 是一个完全背包问题，但求解的是装满背包所需的最少物品数，不必在意具体是组合还是排列。
   1. 确定dp数组以及下标的含义：dp[j]表示背包容量为j时，装满背包所需的最少物品数。
   2. 确定递推公式：dp[j] = min(dp[j], dp[j-coin[i]]+1);
   3. dp数组初始化：dp[j]初始化为最大值
   4. 确定遍历顺序：内外层循环顺序无限制

for(int i=0;i<coins.length;i++){
    //j从coins[i]开始轮，再往前从1开始没有意义，肯定装不上这个硬币
    for(int j=coins[i];j <= amount;j++){
        if(dp[j-coins[i]]!=max){
            //只有初始位不为max，也就是能够达成再装上这个硬币就能装满的结果，才允许换位
            dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
        }      
    }
}

5. 具体推导dp数组：如题目

完全平方数

是一个完全背包问题，但求解的事装满背包所需的最少物品数，不必在意具体是组合还是排列。

  1. 确定dp数组以及下标的含义：dp[j]表示背包容量为j时，装满背包所需的最少物品数。

  1. 确定递推公式：dp[j] = min(dp[j],dp[j-n]+1)

  1. dp数组初始化：dp[0] = 0;

  1. 确定遍历顺序：内外层循环顺序无限制

  1. 具体推导dp数组：如题目

单词拆分
1. 单词字典是物品，字符串s是背包，单词能否组成字符串，就是物品能否将背包装满的问题。拆分时可以重复使用字典中的单词，说明是一个完全背包的问题。
  1. 确定dp数组以及下标的含义：dp[i]，表示字符串长度为i的话，如果dp[i]为true，说明可以拆分为一个或者多个在字典中出现的单词。
  2. 确定递推公式：向前想一小步，如果dp[j]==true，并且[j,i]这个区间的字符串在字典中（把字典转换为set类型，便于直接查找），那么dp[i]=true。
  3. dp数组初始化：dp[0] = true，下标非0的dp元素都初始化为false
  4. 确定遍历顺序：这是一个求解排列数问题，所以要先遍历背包，再遍历物品。
  5. 具体推导dp数组：如题目所示。
多重背包理论基础
将物品个数摊开，转换为0-1背包问题，可以在遍历那里，加上一个循环遍历物品个数
todo：背包问题总结
1. 递推公式总结
2. 遍历顺序总结
打家劫舍I
1. 确定dp数组以及下标的含义：dp[i]表示，考虑下标i(包括下标i在内)的房屋，最多可以偷窃的金额。
2. 确定递推公式：
  1. 偷该房屋：dp[i] = dp[i-2]+num[i]
  2. 不偷该房屋：dp[i] = dp[i-1]
  3. 取最大值：dp[i] = max(dp[i-2]+num[i], dp[i-1])
3. dp数组初始化：dp[0]=num[0],dp[1] = max(num[0], num[1])
4. 确定遍历顺序：从前向后遍历
5. 具体推导dp数组：如题目
6. 优化：利用滚动数组，压缩到三个数组元素空间，甚至两个
打家劫舍II
1. 进阶：第一个房屋和最后一个房屋是紧挨着的
2. 考虑两种情况
  1. 不把首元素列入选择范围
  2. 不把尾元素列入选择范围
3. 其余同打家劫舍I

打家劫舍III

  1. 进阶：房屋的排列类似一颗二叉树
  2. 确定递归函数的参数和返回值
     1. 要求一个节点偷或不偷的两个状态所得到的金钱，那么返回值就应该是一个长度为2的数组。
     2. dp[0] 表示不偷该节点所得到的最大金钱，dp[1]表示偷该节点所得到的最大金钱。
  3. 确定终止条件
     1. 当遇到空节点，无论是偷还是不偷得到的金额都只能为0，所以返回{0,0}
     2. 相当于dp的初始化
  4. 确定遍历顺序
     1. 使用二叉树遍历房屋，因为需要递归后的结果来做下一步计算
  5. 确定单层递归的逻辑
     1. 如果偷当前节点，那么左右孩子就不能偷，即val1 = cur.val + left[0] + right[0];
     2. 如果不偷该节点，左右孩子就可以偷，选择大的偷，val2 = max(left[0] , left[1]) + max(right[0] + right[1]);
     3. 返回节点状态{val1，val2}  
  6. 举例推导dp数组：如题目，最后头结点返回的值，取一个最大值就是最大的金钱值

买卖股票的最佳时机

  1. 贪心：取最左最小值、取最右最大值，得到的差值就是最大利润
  2. 动态规划：
     1. 确定dp数组以及下标的含义：
        1. dp[i] [0] 表示第i天持有股票所得最多现金
        2. dp[i] [1] 表示第i天不持有股票所得最多现金
     2. 确定递推公式：
        1. 第i天持有股票即dp[i] [0] ，可以由两个状态推出来
           1. 第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金，dp[i-1] [0]
           2. 第 i 天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
        2. 如果第i天不持有股票，即dp[i] [1]，也可以由两个状态推导出来
           1. 第i-1天就不持有股票，那么保持现状，即dp[i-1] [1]
           2. 第i天卖出股票，所得的现金就是按照今天股票价格卖出后所得现金：prices[i] + dp[i-1] [0]
     3. dp数组初始化
        1. 由递推公式可得，需要知道dp[0] [0]和dp[0] [1]
        2. dp[0] [0] = -price[0];
        3. dp[0] [1] = 0;
     4. 确定遍历顺序
        1. 从前向后遍历
     5. 举例推导dp数组：如题目所示
  3. 也可压缩至一维数组

买卖股票的最佳时机II

  1. 进阶：区别于I，可以完成尽可能多次的交易
  2. 关键区别----确定递推公式：
     1. 第i天持有股票即dp[i] [0] ，可以由两个状态推出来
        1. 第 i-1 天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金，dp[i-1] [0]
        2. 第 i 天买入股票，所得现金就是买入今天的股票后所得现金，但因为之前做过的交易，会有利润，所以：dp[i-1] [1]-prices[i]
     2. 如果第i天不持有股票，即dp[i] [1]，也可以由两个状态推导出来
        1. 第i-1天就不持有股票，那么保持现状，即dp[i-1] [1]
        2. 第i天卖出股票，所得的现金就是按照今天股票价格卖出后所得现金：prices[i] + dp[i-1] [0]

买卖股票的最佳时机III

  1. 进阶：区别于I，II，只能最多完成两次交易
  2. 确定dp数组以及下标的含义：
     1. 一天中有且仅有五个状态：0不做操作、1第一次持有股票、2第一次不持有股票、3第二次持有股票、4第二次不持有股票
     2. dp[i] [j] ，i表示在第i天，j表示0-4这五个状态，dp[i] [j]表示在第i天状态j所剩的最大现金
  3. 确定递推公式：
     1. 达到dp[i] [1] = max(dp[i-1] [1] , dp[i-1] [0]-prices[i]);
     2. 达到dp[i] [2] = max(dp[i-1] [2] , dp[i-1] [1]+prices[i]);
     3. 达到dp[i] [3] = max(dp[i-1] [3] , dp[i-1] [2]-prices[i]);
     4. 达到dp[i] [4]：max(dp[i-1] [4] , dp[i-1] [3]+prices[i]);
  4. dp数组如何初始化：需初始化 dp[0] [j]，简易理解为当天买入，当天卖出
     1. dp[0] [0] = 0;
     2. dp[0] [1] = -prices[0];
     3. dp[0] [2] = 0;
     4. dp[0] [3] = -prices[0];
     5. dp[0] [4] = 0;
  5. 确定遍历顺序：从前向后遍历
  6. 举例推导dp数组：如题目所示

买卖股票的最佳时机IV

  1. 进阶：区别于I,II,III，最多可以完成K笔交易，所以将会有2*K+1种状态
  2. 易得，除了0以外，**偶数**就是卖出，**奇数**就是买入
  3. 其余同III

最佳买卖股票时机含冷冻期
1. 确定dp数组以及下标的含义：
  1. 状态一：持有股票状态（今天买入股票，或者之前就买入了股票但是没有操作，一直持有）
  2. 不持有股票状态
    1. 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者前一天就是卖出股票状态，一直没操作）
    2. 状态三：今天卖出股票
  3. 状态四：今天为冷冻期状态
2. 确定递推公式：
  1. 达到买入股票状态，即达到状态一：dp[i] [0]
    1. 操作1：前一天是持有股票状态：dp[i] [0] = dp[i-1] [0]
    2. 操作2：今天买入
      1. 前一天是冷冻期（状态四）：dp[i] [0] = dp[i-1] [3]-prices[i]
      2. 前一天是保持卖出股票的状态（状态二）dp[i] [0] = dp[i-1] [1]-prices[i]
  2. 达到保持卖出股票状态，即达到状态二：dp[i] [1]
    1. 操作1：前一天就是保持卖出股票的状态（状态二）dp[i] [1] = dp[i-1] [1]
    2. 操作2：前一天是冷冻期（状态四）dp[i] [1] = dp[i-1] [3]
  3. 达到今天就卖出股票状态，即达到状态三：
    1. 即今天卖出：前一天一定是状态1，dp[i] [2] = dp[i-1] [1]+prices[i]
  4. 达到冷冻期状态，即达到状态四：
    1. 即昨天卖出，dp[i] [3] = dp[i-1] [2]
3. dp数组如何初始化：
  1. dp[0] [0] = -prices[0]
  2. dp[0] [1] = 0
  3. dp[0] [2] = 0
  4. dp[0] [3] = 0
4. 确定遍历顺序：从前向后遍历
5. 举例推导dp数组：如题目所示
6. 可以压缩至一维数组，但是注意提前存储会被改变，但是后面仍需用的前一天的dp值。

买卖股票的最佳时机含手续费

  1. 进阶：每笔交易有一笔手续费，整体同II，只是需要修改递推公式，在卖出的同时再减去一笔手续费

最长递增子序列

  1. 确定dp数组以及下标的含义：dp[i] 表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
  2. 确定递推公式：if(nums[i]>nums[j]) dp[i] = max(dp[i],dp[j]+1);
  3. dp数组如何初始化：每一个i，对应的dp[i] = 1
  4. 确定遍历顺序：从前向后遍历，i在外层，j在内层
  5. 举例推导dp数组：如题目所示

最长连续递增序列

  1. 不同于“最长递增子序列”，需要是**连续递增**的
  2. 动态规划：
     1. 确定dp数组以及下标的含义：dp[i]表示以下标i结尾的连续递增的子序列长度为dp[i]。
     2. 确定递推公式：if(nums[i]>nums[i-1])，dp[i] = dp[i-1]+1;
     3. dp数组如何初始化：每一个i，对应的dp[i] = 1
     4. 确定遍历顺序：从前向后遍历
     5. 举例推导dp数组，如题目所示
  3. 贪心算法：连续++，不连续count从头开始，遍历结尾更新result

最长重复子数组

  1. 确定dp数组以及下标的含义：dp[i] [j] 表示以下标 i-1 为结尾的A和以下标 j-1为结尾的B，最长重复子数组的长度为dp[i] [j]。易得，遍历要从i=1，和j=1开始
  2. 确定递推公式：if(A[i-1]==B[j-1])  dp[i] [j] = dp[i-1] [j-1]+1;
  3. dp数组如何初始化：dp[i] [0]和dp[0] [j] 都需初始化为0
  4. 确定遍历顺序：外层循环A，内层循环B；也可相反
  5. 举例推导dp数组：如题目所示
  6. 如果压缩成一维数组，遍历数组B的时候就需从后向前遍历，避免重复覆盖

最长公共子序列

  1. 确定dp数组以及下标的含义：dp[i] [j] 表示长度为[0,i-1]的text1，和长度为[0,j-1]的text2的最长公共子序列为dp[i] [j]。
  2. 确定递推公式：
     1. text1[i-1] == text2[j-1] ：则有dp[i] [j] = dp[i-1] [j-1] +1
     2. text1[i-1] != text2[j-1]：则有dp[i] [j] = max(dp[i-1] [j]，dp[i] [j-1])
  3. dp数组如何初始化：统一初始化为0
  4. 确定遍历顺序：从前向后，从左向右
  5. 举例推导dp数组：如题目所示

不相交的线
1. 直线不能相交，说明在字符串nums1中找到一个与字符串nums2相同的子序列，且这个子序列不能改变相对顺序，否则直线就会相交，即求解绘制的最大连线数，实际上是求解两个字符串的最长公共子序列的长度。
2. 同上题最长公共子序列
最大子序和
1. 确定dp数组以及下标的含义：dp[i]表示包括下标i在内（即以nums[i]为结尾）的最大连续子序列
2. 确定递推公式：两个方向
  1. nums[i]加入，dp[i] = dp[i-1]+nums[i]
  2. dp[i] = nums[i]，从头开始计数
  3. dp[i] = max(nums[i] , dp[i-1]+nums[i])
3. dp数组如何初始化：dp[0] = nums[0]
4. 确定遍历顺序：从前向后遍历
5. 举例推导dp数组：如题目所示
判断子序列
1. 直接思路，类似最长公共子序列的思路，判断最后dp[len1] [len2]==len1，即最长公共子序列的长度是否等于子序列的长度
2. 编辑距离思路，体现在递推公式上，当s[i-1]!=t[j-1]时，此时就要删掉t[j-1]，也就是让dp[i] [j] = dp[i] [j-1]
不同的子序列
1. 确定dp数组以及下标的含义：dp[i] [j] 表示以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i] [j]（初始化dp数组的时候就要注意，长度应为length+1
2. 确定递推公式：
  1. s[i-1] == t[j-1]，dp[i] [j] = dp[i-1] [j-1] + dp[i-1] [j]
    1. 当使用s[i-1]来进行匹配时，dp[i] [j] =dp[i-1] [j-1]
    2. 当不使用s[i-1]来进行匹配时，dp[i] [j] = dp[i-1] [j]
  2. s[i-1] != t[j-1]，即不使用s[i-1]进行匹配，模拟删除s序列中的这个元素，dp[i] [j] = dp[i-1] [j]
3. dp数组如何初始化：需初始化dp[i] [0] 以及dp[0] [j]
  1. dp[i] [0] =1
  2. dp[0] [j] = 0
  3. dp[0] [0] =1
4. 确定遍历顺序：从上到下，从左到右
5. 举例推导dp数组：如题目所示
两个字符串的删除操作
1. 动规思路1：同最长公共子序列思路，最后求出最长公共子序列的长度，用两个字符串的长度分别减去公共子序列的长度，相加。
2. 动规思路2：用编辑距离的思路，就是两个字符串都可以删除了，会增加一些情况
  1. 确定dp数组以及下标的含义：dp[i] [j] 表示，以i-1为结尾的word1，和以i-2为结尾的word2，想要达到相等，所需要删除元素的最少次数。
  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-1] [j]+1
      2. 删除word2[j-1]：dp[i] [j-1]+1
      3. 都删除：dp[i-1] [j-1]+2
      4. 易得，3可以从1或2推出，即dp[i] [j-1]+1 = dp[i-1] [j-1]+2
  3. dp数组如何初始化：dp[0] [j]和dp[i] [0]都需要初始化
    1. dp[i] [0] = i
    2. dp[0] [j] = j
  4. 确定遍历顺序：从上到下，从左到右
  5. 举例推导dp数组：如题目所示
编辑距离
1. 确定dp数组以及下标的含义：dp[i] [j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离。
2. 确定递推公式：
  1. word1[i-1] == word2[j-1]：dp[i] [j] = dp[i-1] [j-1]
  2. word1[i-1] != word2[j-1]
    1. 操作1：word1删除一个元素 dp[i-1] [j]+1（word2添加一个元素，相当于word1删除一个元素）
    2. 操作2：word2删除一个元素 dp[i] [j-1]+1
    3. 操作3：替换元素，替换word1[i - 1]，使其与word2[j - 1]相同，dp[i-1] [j-1]+1
3. dp数组如何初始化：
  1. dp[i] [0] = i
  2. dp[0] [j] = j
4. 确定遍历顺序：从上到下，从左到右
5. 举例推导dp数组：如题目所示
回文子串
1. 动态规划
  1. 确定dp数组以及下标的含义（容易找到递推关系公式的方向去设置dp数组）
    1. 布尔类型的dp[i] [j]，表示区间范围[i,j]内的子串是否为回文子串，如果是，则true，如果不是，则为false
  2. 确定递推公式：
    1. s[i] != s[j] ，dp[i] [j]一定为false
    2. s[i] == s[j]
      1. 下标i与j相同，同一个字符串a，自然是回文子串
      2. 下标i与下标j相差为1，例如aa，也是回文子串
      3. 下标i与下标j相差大于1，需要判断dp[i+1] [j-1]是否为true
  3. dp数组如何初始化：dp[i] [j]需全部初始化为false
  4. 确定遍历顺序：从下到上，从左到右遍历
  5. 举例推导dp数组：如题目所示
2. 双指针法（todo）
  1. 整体思路：确定回文串，找中心然后向两边扩散看是不是对称的。
    1. 一个元素可以作为中心点，两个元素也可以作为中心点
最长回文子序列
1. 确定dp数组以及下标的含义：dp[i] [j]表示字符串s在[i,j]范围内最长的回文子序列长度
2. 确定递推公式：
  1. s[i] != s[j]
    1. 有可能加入s[j]的回文序列
    2. 有可能加入s[i]的回文序列
    3. dp[i] [j] = max(dp[i + 1] [j], dp[i] [j - 1])
  2. s[i] == s[j] ：dp[i] [j] = dp[i+1] [j-1] +2
3. dp数组如何初始化：手动初始化dp[i] [i]=1（下标相同时），其余情况为0
4. 确定遍历顺序：从下往上，从左往右
5. 举例推导dp数组：如题目所示

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

6-刷题记录

动态规划

动态规划理论基础

斐波那契数

爬楼梯

使用最小花费爬楼梯

不同路径

不同路径II

整数拆分

不同的二叉搜索树

0-1背包理论基础（一）

0-1背包理论基础（二）滚动数组

分割等和子集

最后一块石头的重量II

目标和

一和零

完全背包理论基础

零钱兑换II

组合总和IV

零钱兑换

完全平方数

单词拆分

多重背包理论基础

todo：背包问题总结

打家劫舍I

打家劫舍II

打家劫舍III

买卖股票的最佳时机

买卖股票的最佳时机II

买卖股票的最佳时机III

买卖股票的最佳时机IV

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

买卖股票的最佳时机含手续费

最长递增子序列

最长连续递增序列

最长重复子数组

最长公共子序列

不相交的线

最大子序和

判断子序列

不同的子序列

两个字符串的删除操作

编辑距离

回文子串

最长回文子序列