算法介绍动态规划算法一般分为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. 最长递增子序列