以下关于最长上升子序列（LIS）问题的常规线性动态规划解法的描述，错误的是哪一项？

ir792001 单选题共个子题

最长上升子序列指的是在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能大，子序列不要求元素在原序列中连续。

定义dp[i]表示以原数组第i个元素结尾的最长上升子序列长度，初始化时所有dp[i]的默认值为1

状态转移方程可以写为：对所有满足j < i的下标j，如果nums[i] > nums[j]，则dp[i] = max(dp[i], dp[j] + 1)

该线性DP解法的时间复杂度为O(n)，空间复杂度为O(n)（n为原数组长度）

最终求解得到的最长上升子序列长度是整个dp数组中的最大值

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析