算法介绍
动态规划算法一般分为5 55步：
- 确定状态表示：使用动态规划时，一般需要一个d p dpdp数组，状态表示指的是d p dpdp数组的第i ii个元素d p [ i ] dp[i]dp[i]的含义
- 得到状态转移方程：根据设定好的状态表示和题目，可以得出一个状态转移方程，用于推导d p dpdp表中的值
- 初始化：使用推导出来的状态转移方程填表时，某些位置可能会越界，要先将它们初始化，保证填表不越界。初始化的方法主要有直接初始化，使用空间来简化代码两种
- 填表顺序：根据状态转移方程，确定填d p [ i ] dp[i]dp[i]时需要哪些值，确定填表顺序
- 返回值：根据状态表示，题目要求来确定最终的返回值
子数组问题
子数组指的是原数组中连续的元素所组成的集合。在做子数组问题时，一般状态表示都是通过经验+ ++题目要求得到，经验一般是以某一个位置为结尾，比如以i ii位置为结尾
- 53. 最大子数组和
- 918. 环形子数组的最大和
- 152. 乘积最大子数组
- 1567. 乘积为正数的最长子数组长度
- 413. 等差数列划分
- 978. 最长湍流子数组
- 139. 单词拆分
- 467. 环绕字符串中唯一的子字符串
子序列问题
子序列指的是原数组中连续或不连续的元素所组成的集合，子序列中元素的顺序和原数组中一致。由于子序列包含了子数组，所以要比子数组问题更难。在做子序列问题时，一般状态表示都是通过经验+ ++题目要求得到，经验一般是以某一个位置为结尾，比如以i ii位置为结尾
- 300. 最长递增子序列