§1
题目描述
给定一个未排序的整数数组 nums , 返回最长递增子序列的个数 。 注意 这个数列必须是 严格 递增的。
nums = [1,3,5,4,7]
输出 = 2
§2
思路解析动画文字版
下面 9 步动画会按主解代码推进,而不是泛泛讲题型。
1. 看输入:DP 表跟着代码走:先把示例输入映射到代码参数:def findNumberOfLIS(self, nums):。
2. 初始化:DP 表跟着代码走:开局只立住必要变量:n = len(nums);length = [1] * n;count = [1] * n。
3. 进入主循环:DP 表跟着代码走:主流程从这里开始:for i in range(n):。
4. 判断分支:DP 表跟着代码走:题目条件落到这一行:if nums[j] < nums[i]:。
5. 更新状态:DP 表跟着代码走:对应代码:更新答案变量。这一行决定当前轮对答案有什么贡献。
6. 处理边界:DP 表跟着代码走:边界跟着代码看:if nums[j] < nums[i]:。
7. 继续推进:DP 表跟着代码走:推进语句是:for i in range(n):。处理过的部分不再重新枚举。
8. 准备返回:DP 表跟着代码走:到这里,i 已经能表达题目要求。
9. 答案收束:DP 表跟着代码走:最后检查返回形态:返回值、原地修改或设计类状态,要和 LeetCode 判题方式一致。
记住这题的代码骨架:题意约束先落到状态变量,再用循环或递归维护它。
§3
参考代码
class Solution: def findNumberOfLIS(self, nums): n = len(nums) length = [1] * n count = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: if length[j] + 1 > length[i]: length[i] = length[j] + 1 count[i] = count[j] elif length[j] + 1 == length[i]: count[i] += count[j] longest = max(length) return sum(c for l, c in zip(length, count) if l == longest)看懂代码不等于写得出。盖住上面,自己默写一遍试试。卡在哪一行说不清,就点右下角问小欧。
§4
复杂度
- 时间复杂度:O(n^2),枚举前驱
- 空间复杂度:O(n),长度和计数数组
§5
易错点
✗ 错误写法:只维护长度
✓ 正确写法:同时维护 count
题目要求个数
✗ 错误写法:遇到相同长度覆盖计数
✓ 正确写法:相同长度累加计数
多个前驱都能形成 LIS
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
下一题 · 动态规划套路 23/29
→最长重复子数组
LeetCode 718 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
299道动画图解
37节语音讲解
28课数据结构
¥0.27折合 / 天
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
¥99 开通年卡 →
想成体系刷透这类套路?去图解算法专题