Microsoft 365：动态规划（DP）基础

shaowu459

例题2：
如下图所示，从B2开始，每次只能往右或下走。问：到达D5时经历单元数据最小值。


我们还是逐个单元格来进行分析，看是否能找出规律。
在起点B2单元格时，因为只有一个数值，所以最小值就是7。


从B2走到C2时，累计最小值是C2单元格的8加上左侧的7，结果是15。


从B2走到B3时，累计最小值是B3单元格的8加上方的7，结果是23。


从C2或B3走向C3，累计最小值是多少呢？C3单元格的值肯定是要加上的，如果要使累计到C3单元格的数值最小，只能选择从C2单元格走到C3单元格，因为C2单元格的值小于B3单元格的值。

根据以上的分析，我们可以总结出：如果以dp[i,j]代表到第i行j列单元格的累计最小值，那么dp[i,j]=min(dp[i,j-1],dp[i-1][j])+nums[i,j]。特别的地方在于，如果已经处于第一行或第一列，则只能从左侧或上方的单元格走过来。


上面的例子仅用于说明二维DP的一种最简单的形式，公式实现起来比较长，意义不大，不再探讨。

shaowu459

例题3：
给定一个非0数值组成的数组nums，求连续子序列（至少包括一个数值）和的最大值。



如果以dp表示以第i个元素结尾的连续子序列的和最大值，那么dp要如何才能保证最大呢？通过分析可以知道：
如果dp[i-1]>0，那么dp=dp[i-1]+nums能更大，因为当前数加上一个大于0的数字，结果肯定更大，也就是可以把nums追加在之前的数列尾部。
如果dp[i-1]<0，那么dp=nums能更大，因为如果加上前面小于0的数字结果会比nums还小，因此，从nums开始重打鼓另开张，以nums作为新连续子序列的第一个元素。所以，转移状态方程式：dp=nums+max(0,dp[i-1])

根据上述分析，可以写出以下公式：

1. =MAX(SCAN(,B2:K2,LAMBDA(x,y,y+MAX(,x))))

复制代码

使用SCAN函数获得以每个元素为结尾的连续子序列的最大值，最后再使用MAX提取返回结果中的最大值即可。

shaowu459

例题4：
计算从起点前到终点体力值消耗和的最小值。题目描述见下图（不能连续走两个节点的意思是，这次一下走了两个节点，下次只能再走一个节点，不能再一下走两个节点）：



在任意一个节点看的时候，有两种状态：一种是下次不能走两个节点，这种情况肯定是前一次是一下走了两个节点；一种是下次能走两个节点，这种情况肯定是从前一个节点走过来的。因此，可以设置dp[ i,1]和dp[ i, 2]，dp[ i, 1]代表到下标i且下次不能走两个节点时累计体力消耗最小，dp[ i ,2]代表到下标i且下次能走两个节点时累计体力消耗最小值。下面来具体分析下dp[ i ,1]和d[[2]如何获得。


以到Path7为例，接下来不能走两个节点时体力消耗最小值是Path5的第二种状态消耗体力状态最小值+Path7的体力数值（假设走到这个节点就消耗了当前节点体力值），因为如果在Path7不能走两个节点，只能是从Path5一次性跳两个节点到Path7的。也就是：dp[ i ,1]=dp[i-2][2]+nums


如果在Path7下一次能跳两个节点，说明是从Path6走一个节点过来的，因此，在Path7接下来能走两个节点时体力消耗最小值是前一个节点（Path6）两种状态消费体力的最小值加上当前节点的体力值。也就是：dp[ i ,2]=min(d[i-1][1],dp[i-1][2])+nums



在每个节点情况都是一样的，只不过到第一个节点和第二个节点会稍有问题，我们挨个看一下：
dp[1][1]：

dp[1][2]：


dp[2][1]：

dp[2][2]：


dp[1]和dp[2]都涉及了起始点的值，因此我们可以手动设置一个正确的初始值（根据需要构造），这样，转移状态方程就可以正常推下去了。


结合上面的分析，我们可以写出以下的公式（公式把接下来可走2个节点的结果放在上方，不能走2个节点的结果放在下方）：

1. =MIN(TAKE(REDUCE({1;1}*A2:B2,C2:V2,LAMBDA(x,y,HSTACK(x,VSTACK(MIN(TAKE(x,,-1)),@TAKE(x,,-2))+N(y)))),,-1))

复制代码

公式中使用{1;1}*A2:B2构造了一个初始值作为REDUCE函数的第一参数，然后遍历数组中的每个元素。在遍历过程中，使用VSTACK函数将当前x中最后一列（前一个节点）的最小值和倒数第二列中第一个值（对应接下来能走两个节点情况）纵向堆积起来，然后再使用HSTACK函数堆积在x右侧。遍历完毕后，提取x最后一列，然后取最小值即可。

shaowu459

请注意：由于论坛回复格式设置问题，我在写下面图片里这些内容时，论坛会把方框和里面的i去掉，把字体变成斜体，所以现在帖子有些地方阅读的时候会发现缺失了方框和i。虽然可以通过插入空格来解决，但是改一下就得进审核，暂时不改了。

本题的视频解说在群号为717211831的置顶公告中，有兴趣的可以下载浏览。

静听溪流

搬个板凳坐前排    学习

shaowu459

11楼二维表问题的公式参考：https://club.excelhome.net/threa ... tml?_dsign=d63e94c5