在使用线性动态规划求解数组的最长上升子序列（LIS）问题时，下列说法正确的是？

te800157 单选题共个子题

已知我们定义dp[i]表示以数组第i个元素结尾的最长上升子序列的长度，初始时所有dp[i] = 1，数组长度为n，下标从0到n-1。

状态转移方程可直接写为dp[i] = dp[i-1] + 1，无需判断元素大小关系

对于每个i，需遍历所有j∈[0,i-1]，若nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j]+1)

该线性DP解法的时间复杂度为O(n)，空间复杂度为O(n)

最终的最长上升子序列长度就是dp[n-1]的值，无需额外遍历dp数组取最大值

正在加载题目数据…

第空

已答 /

子题

第空

提示

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

答案解析