动态规划之子序列问题1

以leetcode300题为例

此题最为经典，所有的算法书在讲子序列问题时都以这个为模板题，后面的题可以按照此题的分析方法进行分析

 区分子序列和子数组

例如a，b，c，d，e这个数组

子数组是必须连续的，就比如必须是abc，cde等

子序列不要求连续，只要相对顺序是对的就行，比如ace，abc都是一个子序列

这样来看子序列包括子数组

为什么子序列的问题复杂，因为包含的情况多，

所有的子序列是2^n次方，子数组是是一个等差数列（n+1）*n/2

题目分析

要求严格递增的子序列的最长长度，可以通过实例分析，什么叫严格，就是子序列相邻的两个元素不能相等，像77777，最长的就只能为7，也就是一个长度

算法原理

1.状态表示：经验+题目要求

 经验有两个，像这种线性的可以大概套一下，以i位置为结尾巴拉巴拉（如果后面分析不对，可以换成以i位置为起始，巴拉巴拉）

题目要求：以i位置为结尾的所有子序列中，最长的递增子序列的长度

dp[i]：以i位置元素为结尾的所有的子序列中，最长的递增子序列的长度

2.状态转移方程：以最近的一步划分子问题

分析状态转移方程时，要时刻知道清楚自己的dp[i] 表示什么

你要求的是dp[i]=什么？，也就是找所有包含i位置元素的所有子序列，然后比较得到最长的

可以分两种：1：自己构成一个子序列，也就是1

2：跟在别人后面构成子序列，你可以跟在i-1/i-2/i-3等后面，也就是比较所有跟在这些后面的长度

能跟在的前提是nums[i]>nums[i-1]，因为你求的是最长的递增子序列

 

为什么要初始化为1？因为你最差的情况就是一个元素构成一个子序列，那这样我们填表的时候就不需要分两种情况，只要算其中一种就行，不满足它自动就是1

编写代码