第31208题 单选题
在使用线性动态规划求解长度为n的整数数组的最长递增子序列(LIS)问题时,若定义dp[i]表示以第i个元素结尾的最长递增子序列的长度,下列说法错误的是?

已知数组下标从0开始计数,子序列要求元素严格递增。

A

dp数组的初始值全部为1,因为每个元素本身就是长度为1的子序列

B

状态转移方程为dp[i] = max(dp[j] + 1) ,其中j的范围是0 ≤ j < i 且 nums[j] < nums[i],若无满足条件的j则dp[i]保持初始值

C

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

D

整个数组的最长递增子序列的长度为dp数组中的最大值

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析