动态规划题单（自用）

算法介绍

动态规划算法一般分为5 55步：

1. 确定状态表示：使用动态规划时，一般需要一个d p dpdp数组，状态表示指的是d p dpdp数组的第i ii个元素d p [ i ] dp[i]dp[i]的含义
2. 得到状态转移方程：根据设定好的状态表示和题目，可以得出一个状态转移方程，用于推导d p dpdp表中的值
3. 初始化：使用推导出来的状态转移方程填表时，某些位置可能会越界，要先将它们初始化，保证填表不越界。初始化的方法主要有直接初始化，使用空间来简化代码两种
4. 填表顺序：根据状态转移方程，确定填d p [ i ] dp[i]dp[i]时需要哪些值，确定填表顺序
5. 返回值：根据状态表示，题目要求来确定最终的返回值

子数组问题

子数组指的是原数组中连续的元素所组成的集合。在做子数组问题时，一般状态表示都是通过经验+ ++题目要求得到，经验一般是以某一个位置为结尾，比如以i ii位置为结尾

• 53. 最大子数组和
• 918. 环形子数组的最大和
• 152. 乘积最大子数组
• 1567. 乘积为正数的最长子数组长度
• 413. 等差数列划分
• 978. 最长湍流子数组
• 139. 单词拆分
• 467. 环绕字符串中唯一的子字符串

子序列问题

子序列指的是原数组中连续或不连续的元素所组成的集合，子序列中元素的顺序和原数组中一致。由于子序列包含了子数组，所以要比子数组问题更难。在做子序列问题时，一般状态表示都是通过经验+ ++题目要求得到，经验一般是以某一个位置为结尾，比如以i ii位置为结尾

• 300. 最长递增子序列