关于C++实现线性动态规划经典问题的思路，下列说法正确的是？

qm112259 单选题共个子题

线性动态规划是状态转移呈线性递推关系的动态规划类型，是动态规划中最基础的分类，常见经典问题包括爬楼梯、最长上升子序列（LIS）、最大子数组和、打家劫舍等。

求解爬楼梯问题（每次可爬1级或2级台阶，求到达第n级台阶的总走法数）的状态转移方程可写为dp[i] = dp[i-1] + dp[i-2]，初始条件设为dp[0]=0、dp[1]=1，该问题的空间复杂度最优可降到O(1)

求解长度为n的数组的最大子数组和问题，线性DP的状态可定义为dp[i]表示以第i个元素结尾的最大子数组和，状态转移方程为dp[i] = max(dp[i-1] + nums[i], nums[i])，该解法时间复杂度为O(n)

求解最长上升子序列（LIS）的纯线性DP解法时间复杂度为O(n)，状态转移方程为dp[i] = max{ dp[j] + 1 | 0 ≤ j < i 且 nums[j] < nums[i] }

线性动态规划的所有问题都必须按照从左到右的顺序递推状态，不能采用反向递推的方式设计解法

正在加载题目数据…

第空

已答 /

子题

第空

提示

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

答案解析