300.最长递增子序列
题目
你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
```
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
## 题解
动态规格适用于
- 多阶段决策问题
- 不问具体解，只求最优解
**确定dp数组及其下标的含义**
> 第一次做我是没想出定义时为什么要以nums[i]结尾,看题解也没有想出个所以然。这里先了解，定义dp数组之后后面就好做多了。
dp[i] = 以nums[i]结尾的数组最长严格子序列长度为dp[i]
**确定递推式**
当前元素是nums[i],dp[i]如何推出？
- 如果nums[i]>nums[i-1],dp[i] = dp[i-1]+1;
- 如果nums[i]<=nums[i-1],dp[i] = dp[i-1];
开始是上面那样想的是因为对dp数组的定义有问题，然后报错之后发现
不应该只比较nums[i-1],因为我们**维护的是最长的子序列**，我们应该判断当前nums[i]与之前的最长递增子序列最后一个元素，最长递增子序列的最后一个元素不一定是nums[i-1]。
那么最长子序列的最后一个元素是什么呢？在i之前的每一个元素都有可能是最长子序列的最后一个元素。
所以与nums[j]比较，其中j<i,如果nums[i]>nums[j]，说明当前元素可以加入以nums[j]结尾的最长递增子序列后面构成新的，dp[i] = dp[j]+1。
对于当前dp[i]，不断地和dp[j]+1比较，寻找最大值 nums[i]>nums[j],dp[i] = Math(dp[i],dp[j]+1);
**dp数组初始化**
以nums[i]结尾的最长子序列至少要包含自己，那么dp数组初始化应该为1
**确定遍历顺序**
```java
for(int i=1;i<nums.length;i++){
for(int j=0;j<i;j++）{
if(nums[i]>nums[j]) dp[i]= Math.max(dp[i],dp[j]+1);
}
if(result>dp[i]) result = dp[i];
}
代码
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if(len<=1) return 1;
int dp[] = new int [len];
dp[0] = 1;
int result = 0;
for(int i=1;i<nums.length;i++){
dp[i] = 1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]) dp[i]= Math.max(dp[i],dp[j]+1);
}
if(dp[i]>result) result = dp[i];
}
return result;
}
}
子序列问题
子序列问题
- 子序列（不连续）
- 子序列（连续）
- 编辑距离
- 回文