动态规划

题目分析 本题首先规定了游戏规则如下： 将当前余下的石头分成左右非空的两部分； 分别计算两部分的石头价值总和，若两者不等，则保留总和较小的一部分，否则任选一部分保留； 将留下的石子价值总和计入$Alice$的得分； 按照上述规则一直进行游戏，直到只剩下一个石子为止。求$Alice$的最大得分。 基本思路 如果进行了一次分割，那么无论最终留下哪一部分，其实问题都变成了一个规模更小但相似的子问题，故可以想到用动态规划进行解决，定义动态规划数组$dp$，其中$dp[i][j]$表示在区间$[i,j)$中$Alice$能够取得的最大得分，那么将$k$在$(i,j)$中遍历，则$dp[i][j]$的计算需要分以下两种情况： 为方便叙述，记$stoneValues[i:k]$的总和为$left$，$stoneValues[k:j]$的总和为$right$。 $$ dp[i][j] = max \begin{cases} dp[i][k]+left &,left\leq right\\ dp[k][j]+right &,left\geq right \end{cases} $$不难发现，由于$stoneValues$中的所有值都是正数，那么随着$k$的增加，$left$必定越来越大，$right$必定越来越小，故一定存在下标$p$，使得当$k\in (i,p]$时均满足$left\leq right$，同理，一定存在下标$q$，使得当$k \in [q,j)$时均满足$left \geq right$，可以发现，当存在一个$k$使得$left=right$时，$q=p$，否则，$q=p+1$。 因此，如果用前缀和数组$s$表示出$left$和$right$，并结合上述分析即可得到： $$ dp[i][j] = max \begin{cases} \max\limits_{k=i+1}^{p}(dp[i][k]+s[k]-s[i])\\ \max\limits_{k=q}^{j-1}(dp[k][j]+s[j]-s[k]) \end{cases} $$将与$k$无关的项提取出来即可得到： $$ dp[i][j] = max \begin{cases} -s[i]+\max\limits_{k=i+1}^{p}(dp[i][k]+s[k])\\ s[j]+\max\limits_{k=q}^{j-1}(dp[k][j]-s[k]) \end{cases} $$可以发现，后面求最大值的项中，$k$都是在区间$[i,j]$的前缀或后缀中遍历的，故如果能维护一个特定区间中指定式子的前缀最大值和后缀最大值，就可以快速求出$dp[i][j]$的值，定义前缀最大值数组$preMax[i][j]$表示$\max\limits_{k=i+1}^{j}(dp[i][k]+s[k])$，同时定义后缀最大值数组$sufMax[i][j]$表示$\max\limits_{k=i}^{j-1}(dp[k][j]-s[k])$，那么上面的递推关系式就变成了： $$ dp[i][j] = max \begin{cases} -s[i]+preMax[i][p]\\ s[j]+sufMax[q][j] \end{cases} $$同时根据定义可以得知$preMax$和$sufMax$数组的递推关系如下： $$ \begin{align} preMax[i][j] = max(preMax[i][j-1], dp[i][j]+s[j])\\ sufMax[i][j] = max(sufMax[i+1][j], dp[i][j]-s[i]) \end{align} $$有了递推关系式，接下来就需要确定区间左右端点遍历的顺序，注意到，在计算$preMax$的值时，位置$(i,j)$是由位置$(i,j-1)$转移过来的，说明$j$的遍历应当从前往后遍历，同时在计算$sufMax$的值时，位置$(i,j)$是由位置$(i+1,j)$转移过来的，说明$i$的遍历应当从后往前遍历。不过需要注意的是，并不是两个数组中的值都需要在$dp[i][j]$计算完毕后才更新，因为在计算$dp[i][j]$时，实际上需要用到一个$preMax[i][p]$，而$p$是在$i$之后的，故应当在向后计算$p$的位置时同步更新$preMax$中的值。 最后在$dp$中所有值计算完毕后，返回$dp[0][n]$即为答案。 实现细节 如果对于每一个区间都用遍历去寻找$p$和$q$的位置，时间复杂度则会到达$O(n^3)$，故需要将其简化，注意到当确定区间左端点$i$之后，由于$j$的遍历顺序是从前往后，因此$p$和$q$的位置一定是不断右移的，故对于每一个固定$i$的循环，都可以初始化一个$p$的位置，随着$j$的增加，每次都用while循环增加$p$直到满足要求，这样，对于每一个不同的$i$，$p$最多也就循环$n$次，而非暴力的$n^2$次，复杂度即可降为$O(n^2)$。 ...

竞赛链接：2026年浦东新区人工智能创新应用竞赛 如打不开，本文最后有原题截图。 题目分析 本题要求的是工程师的最小移动距离，并且其移动路径应满足： 起始点可以任选； 先检修低阶段的设备，再检修高阶段的设备。 同时，要检修一个设备$i$，工程师的位置必须处在$[segments[i][1], segments[i][2]]$范围内。 基本思路 由于检修设备的阶段应当保持非递减顺序，因此应当按照阶段对所有设备进行分组，并先将低阶段的组内所有设备检修完毕后，才去检修高阶段设备。 检修单个阶段内所有设备 现在先考虑对于一个阶段内的所有设备，如何才能够使将其检修完所移动的距离最小化。这时候就需要将所有可能性划分成两种情况： 这些设备所覆盖的区间均有交集，这时，如果工程师站在这个交集内，他即便是完全不移动，也可以检修完这个区间内的所有设备。并且可以发现：这个交集区间的左端点是所有区间左端点的最大值，右端点则是所有区间右端点的最小值。具体如下图： 这些设备所覆盖的区间并没有交集，这时，工程师无论如何都需要移动，但他移动的最小距离是什么呢？可以发现，如果同样求出来所有区间左端点的最大值$L_{max}$和右端点的最小值$R_{min}$(这时一定是$R_{min} < L_{max}$)，那么工程师向左只需要移动到$R_{min}$的位置即可检修左侧需要走最远的设备，同时向右只需要移动到$L_{max}$的位置即可检修右侧需要走最远的设备，因此在这种情况下，工程师至少要走过区间$[R_{min}, L_{max}]$中的所有点，才能处理完所有设备。具体如下图： 综上所述，无论如何都要求出来一个阶段内的左端点最大值和右端点最小值，才能知道处理完这个阶段的所有设备最少需要移动的距离，以及这个移动距离适用的起点范围。 整合多个阶段并计算最小移动距离 有了检修单个阶段内所有设备的最小移动距离，接下来要求的就是将每个阶段连接起来所需要的最小移动距离。按照阶段从小到大处理，对于第$i$大的阶段，如果能够知道从第$i-1$大的阶段转移到当前阶段所需要的最小移动距离，那么问题就转换成了处理第$i-1$大的阶段及之前所有阶段所需要的最小移动距离，这么看来，可以用动态规划来解决该问题。 定义动态规划数组$dp$，其中$dp[i]$表示检修完第$i$大阶段以及之前所有阶段中所有设备所需要的最小移动距离，并且$dp[i]$中存储着多个三元组$[cost, l, r]$，表示在完成这些任务后，工程师到达区间$[l,r]$中任意一个位置所需移动距离均为$cost$。 考虑转移方程，对于第$i$大阶段的处理，总共有以下两种情况： 该阶段内所有区间均有交集，且交集区间为$[L_{max}, R_{min}]$。这样，遍历$dp[i-1]$中的所有数据$[c_{i-1}, l_{i-1}, r_{i-1}]$，总共分三种情况进行讨论： $R_{min} < l_{i-1}$，也就意味着遍历到的这个上一个阶段对应的区间是在当前交集区间右侧的，而只要移动到这个交集区间内就可以不做任何移动处理完所有设备，因此可以从上一个阶段区间的左端点移动到当前交集区间的右端点，这样总共移动的距离就是$c_{i-1}+l_{i-1}-R_{min}$，同时这个距离只能适配一个位置$R_{min}$，故$dp[i]$中应当加上$[c_{i-1}+l_{i-1}-R_{min}, R_{min}, R_{min}]$； $r_{i-1} < L_{max}$，也就意味着上一个阶段遍历到的区间在当前交集区间左侧，与上面的情况同理，需要从上一个区间的右端点移动到当前交集区间的左端点才能使总移动距离最小，故总共移动距离就是 $c_{i-1}+L_{max}-r_{i-1}$，同样，这个距离也只对应一个位置$L_{max}$，故$dp[i]$中应加上$[c_{i-1}+L_{max}-r_{i-1}, L_{max}, L_{max}]$； 剩下情况一定意味着两个区间有交集，那么如果工程师能够处在这两个区间的交集中，他就不需要移动也可以处理完当前阶段内的所有设备，对应的，$dp[i]$中应当加上$[c_{i-1}, max(l_{i-1}, L_{max}), min(r_{i-1}, R_{min})]$。 该阶段所有区间并没有交集，即$R_{min} < L_{max}$，并且工程师至少要经过区间$[R_{min}, L_{max}]$内的所有位置，因此同样遍历$dp[i-1]$的所有数据$[c_{i-1}, l_{i-1}, r_{i-1}]$，分两种情况讨论，注意每种情况需要先遍历一遍求出最小距离后才加入$dp[i]$中： 如果要先到$R_{min}$，再到$L_{max}$，就要找到区间$[l_{i-1}, r_{i-1}]$中的所有位置到$R_{min}$的最短距离，加上$c_{i-1}$，再加上区间$[R_{min}, L_{max}]$的长度，即为当前情况下处理完第$i$大阶段的最小移动距离 （注意：这个距离适配的位置只有$L_{max}$，故加入$dp[i]$时三元组的区间应为$[L_{max},L_{max}]$）； 如果要先到$L_{max}$，再到$R_{min}$，就要找到区间$[l_{i-1}, r_{i-1}]$中的所有位置到$L_{max}$的最短距离，加上$c_{i-1}$，再加上区间$[R_{min}, L_{max}]$的长度，即为当前情况下处理完第$i$大阶段的最小移动距离 （注意：这个距离适配的位置只有$R_{min}$，故加入$dp[i]$时三元组的区间应为$[R_{min},R_{min}]$）。 最终返回最后一个$dp$列表中每个三元组中代价的最小值即可。 实现细节 需要注意的是，在动态规划转移方程的情况2的两个子情况中，需要求一个区间$[l,r]$中任意一点到达一个位置$x$的最短距离，可以用一个小函数来分情况计算： $x < l$，则返回$l-x$； $r < x$，则返回$x-r$； 否则，$x$在区间中，返回0. 复杂度 时间复杂度：$O(n\cdot logn)$ 空间复杂度：$O(n)$ ...

题目分析 本题需要首先在数组$nums$中选择一个子数组，并对其中所有元素都乘以或除以$k$，之后在整个数组中选出一个最大的子数组总和。 基本思路 贪心(无法通过) 如果要完全按照题目的顺序进行模拟计算，太过复杂，并且选择所有可能的子数组分别计算的时间复杂度太高，因此正难则反，既然要操作以后求最大的子数组总和，那为什么不能先求出原先$nums$中的最大子数组总和，然后再通过乘除$k$得到最后的答案呢？ 理论上这是可以的，如果已知原先$nums$中的最大子数组总和为$maxSum$，那么答案就有两种情况： 当$maxSum>0$时，为了让最终的答案尽可能的大，就需要将其乘以$k$，即答案为$maxSum\times k$； 当$maxSum<0$时，为了让答案尽可能大，则需要将其除以$k$，即答案为$\lceil \frac{maxSum}{k} \rceil$； 因此根据上面的分析可以简单写出以下贪心代码： class Solution: def maxSubarraySum(self, nums: List[int], k: int) -> int: sum_num = nums[0] max_sum_num = nums[0] for i in nums[1:]: if sum_num < 0: sum_num = 0 sum_num += i max_sum_num = max(sum_num,max_sum_num) if max_sum_num > 0: max_sum_num *= k else: max_sum_num = -(abs(max_sum_num)//k) return max_sum_num 可惜的是，在提交之后，上面代码并不能通过全部测试用例，而是卡在了$717/718$的位置上，一直到竞赛结束后才发现那个测试用例长这样： $$ \begin{align} &nums = \underbrace{[-8,5,-8,10,-8,5,-8,10,\dots,-8,5,-8,10]}_{总共100个-8,5,-8,10循环}\\ &k = 5 \end{align} $$按照上面的贪心算法，首先在$nums$中求出最大子数组和，可以得到$maxSum=10$，之后根据判断条件，即可得到最终的答案是$maxSum\times k=50$，但这并不是正确答案，原因在于如果在原数组中先找最大子数组和，寻找过程中会发现单独一个循环节的和是： $$ -8+5-8+10=-1 $$ 但如果将所有数字都按照题目要求的方式整除$k=5$后，上面的四个数字就会变成： $$ \begin{align} -8&\rightarrow -1\\ 5&\rightarrow 1\\ 10&\rightarrow 2\\ \end{align} $$ 于是四个数字相加就变成了： ...

题目分析 本题实际上要求的是满足以下条件的数组数量： 长度为给定值$n$； 每一个值都在限定范围$[l,r]$内； 相邻两个位置的关系从左到右依次增减交替变化。 基本思路 动态规划思路 由于本题要保证的只是数字的大小关系，并没有强制要求按照区间$[l,r]$进行计算，因此为了简便计算，可以将$l$和$r$都减少$l$，使区间变为$[0,r-l]$，这和原有情况是等价的。 本题要求最终的数组长度为$n$，如果此时确定第$n$个数字是$x$，并且确定最后两个数字呈上升趋势，那么就可以确定第$n-1$个数字的取值范围，这样，问题其实变成了一个相似但规模更小的问题。因此可以使用动态规划来解决该问题。仿照上面的分析，可以定义两个动态规划数组如下： $dp0[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈上升趋势的情况下，数组的总数量； $dp1[i][j]$表示数组长度为$i$且第$i$个数字为$j$时，最后两个数字呈下降趋势的情况下，数组的总数量。 这样，答案就应该是$sum(dp0[n])+sum(dp1[n])$。 那么对于$dp0[i][j]$，由于最后两个数字呈上升趋势，因此可以确定第$i-1$个数字的取值范围为$[l,j-1]$，并且第$i-2$和第$i-1$个数字必须呈下降趋势，故可得递推公式如下： $$ dp0[i][j] = \sum_{k=l}^{j-1}dp1[i-1][k] $$类似的，对于$dp1[i][j]$，也可以得到递推公式如下： $$ dp1[i][j] = \sum_{k=j+1}^{r}dp0[i-1][k] $$根据上面两个公式，即可写出动态规划代码。观察到在递推关系式中用到了区间求和，因此可以用前缀和来优化，当加上前缀和优化时，本题目的第$I$题即可通过了。 矩阵乘法和快速幂优化 观察上面两个递推式子，不难发现，如果将$dp0[i]$和$dp1[i]$合并成一个长度为$2 \times (r-l+1)$的数组$dp[i]$，那么每一个$dp[i]$实际上都可以用同样一个公式从$dp[i-1]$中计算得来，而如果将$dp[i]$看作一个维度是$2 \times (r-l+1)$的空间中的一个坐标，那么上面说的这个递推公式其实可以看作一个坐标变换矩阵，每次只需用同样的矩阵乘以原来的坐标，即可得到新的坐标。 （注意，两个数组经过上述合并后，$dp0$中原有的索引不变，但$dp1$中原有的索引会增加$r-l+1$。为叙述方便，定义$k = r-l+1$） 举个例子，如果$k=2$，也就意味着数组中的每个位置上都只有两个数字可以选，那么根据之前的递推公式可以得到： $dp0[i][0] = 0$; $dp0[i][1]=dp1[i-1][0]$; $dp1[i][0]=dp0[i-1][1]$; $dp1[i][1] = 0$. 而如果将$dp0[i][x]$换成$dp[i][x]$，并将$dp1[i][x]$换成$dp[i][x+k]$，即可得到以下递推式： $dp[i][0] = 0$; $dp[i][1] = dp[i-1][2]$; $dp[i][2] = dp[i-1][1]$; $dp[i][3] = 0$; 因此可以整理出从$dp[i-1]$转成$dp[i]$所需要进行的坐标变换矩阵如下： $$ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix} $$总结规律，可以发现，对于任意一个$k$值，对应的坐标变换矩阵都可以按照下面方式列写： ...