LeetCode题解【2140. 解决智力问题：逆序动态规划】

题目概述给定一个二维数组questions其中questions[i] [points_i, brainpower_i]。对于第i道题我们有两种选择解决这道题获得points_i分但接下来必须跳过brainpower_i道题跳过这道题不获得分数继续考虑下一道题。要求返回能够获得的最高分数。这道题本质上是一个典型的「选或不选」动态规划问题。难点在于如果选择当前题后续可选择的位置不是i 1而是i brainpower_i 1。思路分析对于每一道题我们都需要判断做当前题收益是多少不做当前题收益是多少然后取两者的最大值。假设当前处理到第i道题。如果跳过第i道题那么答案就等价于从第i 1道题开始能获得的最大分数。如果解决第i道题可以立即获得questions[i][0]分但是接下来要跳过questions[i][1]道题因此下一道可以继续选择的题目下标为iquestions[i][1]1如果这个下标没有越界那么做当前题的总收益就是questions[i][0]dp[iquestions[i][1]1]如果越界说明做完当前题后已经没有题目可以继续做了那么收益就是当前题本身的分数。状态定义定义dp[i]表示从第i道题开始能够获得的最大分数。最终答案就是dp[i]也就是从第0道题开始能够获得的最大分数。状态转移对于第i道题有两种选择。1. 不做当前题跳过当前题直接从下一题开始dp[i 1]2. 做当前题获得当前题分数questions[i][0]然后跳到下一道允许作答的题目next i questions[i][1] 1如果next n则questions[i][0] dp[next]如果next n则questions[i][0]因此状态转移方程为dp[i] max(不做当前题的收益, 做当前题的收益)展开后就是dp[i] max(dp[i 1], questions[i][0] dp[next])其中需要注意next越界的情况。为什么要倒序 DP因为dp[i]的计算依赖于后面的状态dp[i 1]dp[i brainpower_i 1]这些位置的下标都比i大。所以我们应该从后往前计算保证在计算dp[i]时它依赖的状态都已经被计算出来。这也是这道题适合使用逆序动态规划的原因。代码实现classSolution{public://可以替换为 using LL long long;typedeflonglongLL;LLmostPoints(vectorvectorintquestions){intnquestions.size();// dp[i] 表示从第 i 道题开始最多可以获得的分数// 由于总分可能超过 int 范围因此使用 long longvectorLLdp(n,0);// 最后一题没有后续题目// 如果从最后一题开始最优选择一定是做它dp[n-1]questions[n-1][0];// 从倒数第二题开始向前推// 因为 dp[i] 依赖的是 i 后面的状态for(intin-2;i0;i--){// 当前题做完后需要跳过的问题数量intindexquestions[i][1];// 当前题可以获得的分数intscorequestions[i][0];// 做完当前题之后下一道可以继续选择的题目下标intnextiindex1;// 情况一做当前题后已经没有后续题目可以做if(nextn){// 两种选择// 1. 不做当前题收益为 dp[i 1]// 2. 做当前题收益为 scoredp[i]max(dp[i1],(LL)score);}// 情况二做当前题后还能继续从 next 位置开始选择else{// 两种选择// 1. 不做当前题收益为 dp[i 1]// 2. 做当前题收益为 score dp[next]dp[i]max(dp[i1],(LL)scoredp[next]);}}// 从第 0 道题开始能获得的最大分数returndp[0];}};细节说明1. 为什么dp要用long long每道题的分数可能较大题目数量也不少。如果全部使用int在累加分数时可能会溢出。因此dp数组使用long long更稳妥。同时在进行加法或比较时也需要将score转换为long long(LL)scoredp[next]2. 为什么最后一题初始化为它本身的分数对于最后一道题来说后面已经没有其他题目了。如果从最后一道题开始考虑只有两种选择跳过它得分为0做它得分为questions[n - 1][0]。因为题目分数为正数所以最优选择一定是做最后一题。因此dp[n - 1] questions[n - 1][0]3. 边界情况如何处理当做完当前题后下一道可选题目的下标为nextiquestions[i][1]1如果next n说明已经越过数组范围后面没有题目可以继续做。此时做当前题的收益只有当前题分数score否则做当前题的收益为score dp[next]复杂度分析时间复杂度O(n)只需要从后往前遍历一遍数组每个位置的状态转移都是常数时间。空间复杂度O(n)使用了一个长度为n的dp数组总结这道题的核心在于把问题转化为「从当前位置开始能获得的最大分数」。对于每一道题都只有两种选择不做当前题转移到dp[i 1]做当前题获得当前分数并跳转到dp[i brainpower_i 1]。由于当前状态依赖后面的状态所以采用逆序动态规划从后往前计算即可。整体思路并不复杂但需要特别注意两个细节做当前题后跳转下标是否越界分数累加可能超过int范围需要使用long long。掌握了这两个点这道题就可以比较自然地写出线性复杂度的解法。