第31214题 单选题
对于长度为n的整数数组nums的最长严格上升子序列(LIS)问题,若定义dp[i]表示以nums[i]结尾的最长严格上升子序列的长度,初始所有dp[i]=1,下列线性DP状态转移方程正确的是?

注:子序列指可以通过删除数组中某些或不删除元素,且不改变剩余元素顺序得到的序列,不需要连续。

A

dp[i] = max(dp[i], dp[j] + 1),遍历范围为0≤j<i,无额外判断条件

B

dp[i] = max(dp[i], dp[j] + 1),遍历范围为0≤j<i,且满足nums[j] < nums[i]

C

若nums[i] > nums[i-1]则dp[i] = dp[i-1] + 1,否则dp[i] = dp[i-1]

D

dp[i] = max(dp[0...i-1]) + 1,无额外判断条件

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