dp--300. 最长递增子序列/medium 理解度C

1、题目

给你一个整数数组 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

 

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

2、题目分析

动态规划的解决套路可分为 2 步，①基于问题能定义出状态，②状态间具备动态规划的三个特性

①基于问题定义出状态：（参考该文完成分析：dp–139. 单词拆分 https://blog.csdn.net/fujuacm/article/details/135408092）

②状态间具备动态规划的三个特性（参考该文完成分析：dp–139. 单词拆分 https://blog.csdn.net/fujuacm/article/details/135408092）

1. 重复子问题且重复策略
   重复子问题：
2. 最优子结构
   重复策略&最优子结构：
3. 无后效性
   更前的状态不影响当前状态：
   后面的状态不影响当前状态：

3、解题步骤

dp五部曲
1.定义dp数组以及下标的含义
dp[i]，表示截止到第i个字符，最长递增子序列的长度

2.推导状态转移方程
dp[i] = Math.max(dp[0], dp[1],…, dp[i - 1]) nums[i] > nums[j]

3.初始化dp数组
dp数组，初始化为1，表示截止到自己，最长递增子序列长度为1，即子序列中只包括自己

4.确定遍历顺序（二维dp可以通过 状态转移方程+4宫格明确i、j遍历顺序）
i从1到n。即从第1个字符推导到最后1个字符

5.举例推导dp数组

4、复杂度最优解代码示例

    public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);int max = 1;for (int i = 1; i < nums.length; i++) {for (int j = i - 1; j >= 0; j--) {if (nums[i] > nums[j]) {// 踩坑：在找到首个 nums[i] > nums[j] 后，不能直接退出，而是要接着把状态遍历完。// 举例数据集合= 0 1 0 3，// 在计算到3的最长递增序列时，首先会发现第2个0小于3，而第2个0的dp值为1，故3的dp值是2。// 而其实3的dp值最大可以由1这个值的状态转移而来，因为1的dp值是2，由1转移到3，则3的dp值是3。dp[i] = Math.max(dp[i], dp[j] + 1);}}max = Math.max(max, dp[i]);}return max;}

5、抽象与扩展

通用动态规划的解法，见标题二