文章目录子序列一维dp数组题目 最长递增子序列题目 摆动序列题目最长递增子序列的个数回文子串二维dp数组题目字符串中回文子串的个数题目回文串分割题目最小切割次数子序列一维dp数组首先子序列和子数组是不一样的。数组是连续的而子序列是可以连续/也可以不连续只要元素的相对顺序正确就可以子数组连续子序列连续不连续都可以所以关系是子序列里面包含着子数组题目 最长递增子序列状态表示dp[i]表示以i位置为结尾的所有子序列中最长递增子序列的长度状态转移方程1就i元素一个长度为12前面的序列nums[i]所组成的序列dp[j] 1j∈[0 , i-1]。表示i跟在i-1后面(从0开始到i-1为结尾中间有的元素可能被删除)、i-2后面、i-3后面……0后面。此时通过循环要找到dp[0]到dp[i-1]中长度最长的一个序列将它的长度作为dp[j]初始化可以将dp表里的值刚开始初始化为最差的情况即1这样做长度为1的情况就不需要考虑了已经初始化了填表顺序填dp[i]时依赖dp[0]到dp[i-1]的值所以填表顺序是从左到右返回值dp表里的最大值题目 摆动序列题目最长递增子序列的个数预备知识在数组中找到最大值出现的次数一次遍历解决预设最大值是第一个数出现的次数是11如果nums[i] maxval次数12如果nums[i] maxval不做处理循环会自动i3如果nums[i] maxvalmaxval更改count又变为1回文子串二维dp数组动态规划回文子串空间和时间复杂度都是n的平方状态表示将字符串中所有的子串是否是回文子串的信息保存在dp表中状态转移方程dp[i][j] 如果arr[i] ! arr[j]第一个和最后一个不相等那么一定不是回文子串如果arr[i] arr[j]第一个和最后一个相等分为3种情况题目字符串中回文子串的个数回文子串无需初始化因为特殊情况(比如ij或i1j已经单独判断过了填表顺序dp[i][j]需要根据dp[i1][j-1]来判断dp[i1][j-1]是dp[i][j]的左下角所以填表顺序是(一行一行的)从下往上从左往右返回值回文子串个数题目回文串分割题目最小切割次数