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

0. 动态规划

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

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

如何得到呢？

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

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

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

梳理一下：

五个思考步骤 和 注意事项

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

技巧

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

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

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

       str = '-' + str;
       

   • 为越界的位置增加一个 if() 判断，会稍微改变一点 dp 转移方程的结构
5. 对于用最大或最小值初始化时会有一个计算后溢出的问题，强烈建议使用这个数据 ±0x3f3f3f3f（int 最大值的一半）

优化思路

滚动数组，只留下所需状态求下一个状态，滚动进行。需要注意的是，滚动复制的顺序不能被覆盖。
此种优化对于算法本身不是很重要，可以作为了解。

---

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 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。