【算法】动态规划（dp问题），持续更新

0. 动态规划

介绍本篇之前，我想先用人话叙述一般解决动态规划问题的思路：

动态规划的问题，本身有许多产生结果的可能，需要在具体题目下得到满足某个条件的解。

如何得到呢？

我们就需要根据这个具体问题，建立一个状态表（dp 表），在这张 dp 表中的每一个位置的数据都有明确的、相同的定义，称为 状态表示，而储存的每个数据，就是由原问题产生的每一个子问题的解。

子问题的解又该怎么得到呢？

这就需要通过对子问题如何推导（状态的转移过程）进行具体分析，要求是每个解都能由前一个解得到，从而得到所有的子问题的解。根据得到的解把 dp 表填满，最后就能在这张 dp 表中找到我们要的具体答案。

梳理一下：

🎯五个思考步骤 和 注意事项

• 状态表示：自定义一下 dp 表里的每个数据（子问题的解）有什么统一的含义，就是 dp[i] 是什么
  • dp 表可能是一维数组、二维数组…需要具体分析进行选择
  • 这里的含义需要我们根据题目和经验得出，这里就给大家一个分享一个经验，你可以试着把 i 位置定义成 “以 i 位置为结尾 / 为开头的 xxxx”
• 状态转移方程：一个通用公式，可以用 最近一步 已知状态推出下一个状态，最终达到填满 dp 表的所有状态（即得到所有子问题的解）
• 初始化：保证填表时不越界（根据状态转移方程看哪里有越界的可能，再决定怎么初始化）
• 填表顺序：为了填表时，所需要的状态是已知的
• 返回值：题目要求 + 状态表示

🎯技巧

1. 如果 dp[i] 有例如 “选 / 不选” 两种或多种状态，那么建立两个或多个dp表，也可以把几个表写成二维数组
2. 巧妙利用数组元素和数组下标（尤其是对于 “无序 + 重复” 数据可用）
   • eg：下标对应原数据，元素对应出现个数 / 总合…（见题 1.5）
3. 画出每种状态的转移方程（状态机），对照图去写 dp 转移方程会更加清楚，不容易出错。
4. 初始化：
   • 多加一位数 / 一行 / 一列

     • 此种情况需要注意对原数组访问的时候下标还需要多减一位

     • 如果原数组是字符串，可以对原数组加一个虚拟位置（见题1.4），如下

       str = '-' + str;
       

   • 为越界的位置增加一个 if() 判断，会稍微改变一点 dp 转移方程的结构
   • 对于用最大或最小值初始化时会有一个计算后溢出的问题，强烈建议使用这个数据 ±0x3f3f3f3f（int 最大值的一半）
5. 对于 “环形xx” 想办法转成普通线性关系会简单很多

优化思路

1. 滚动数组，只留下所需状态求下一个状态，滚动进行。需要注意的是，滚动复制的顺序不能被覆盖。
   ps:此种优化对于算法本身不是很重要，可以作为了解。
2. 涉及到类似字典搜索，考虑插入后用 hash 表搜索。（见题 1.4）

---

1. 子数组系列

分析状态时的通用方法：

1. 分成 自身、自身+之前一个元素 进行具体考虑
2. 如果题目和数字有关，分成 >0、<0 进行考虑

---

1.1 乘积为正数的最长子数组长度

🔗详解点击

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。

---

1.2 等差数列划分

🔗详解点击

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的子数组个数。 
子数组是数组中的一个连续序列。

---

1.3 最长湍流子数组

🔗详解点击

给定一个整数数组 arr ，返回 arr 的最大湍流子数组的长度 。
如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组 。
ps: 就是元素两两之间的增长情况是 ↗↘↗↘↗.... 这样

---

1.4 单词拆分

🔗详解点击

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。
请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

---

1.5 环绕字符串中的子字符串

🔗详解点击

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，
所以 base 看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

---

2. 子序列系列

需要和子数组区别，子序列两个要求是：不改变原序列顺序，不要求连续取数
分析状态时的通用方法：

1. 分成 自身、自身+之前一个元素 进行具体考虑；
2. 由于取数不连续，除了分析 dp[] 表中 i 位置，还需要一个 j 位置，确定子序列结尾的前一个元素。时间复杂度是 n²

---

2.1 最长递增子序列

🔗详解点击

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而 不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

---

2.2 摆动序列

🔗详解点击

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。
第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。