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

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

A

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

B

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

C

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

D

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

程序运行统计
暂无判题统计
知识点：
C++算法-线性动态规划
提交0次 正确率0.00%
答案解析
上一题 下一题