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

shaowu459

什么是动态规划

动态规划（Dynamic Programming）是美国数学家里查德·贝尔曼（Richard Bellman）在20世纪50年代提出的一种概念，是一种解决最优化、搜索和计数问题的通用且强大的算法设计技术。DP核心是：将一个问题分解成多个更为简单且有可能重复和重叠的子问题，存储它们的解，通过将其结合在一起，最终得到原始问题的解决方案。

本帖旨在介绍动态规划（DP）的基本概念和使用Microsoft 365函数实现的基础方法。关于动态规划概念及其他主要文字性描述主要来源于网络。

shaowu459

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

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

shaowu459

首先，说明一下动态规划这个名字的来源。


英文Dynamic Programming，中文翻译“动态规划”，但其实对所谓动态和规划都没有那么高深，Bellman，也就是”发明"了DP的人，自己说这个名字是他“编的”，主要为了规避军方的厌恶，否则就要用什么decision making这种名字了。Bellman是个数学家，这里programming不是编程的意思，而是规划、制定计划或决策（现在多用于数学、计算机科学领域）。“Dynamic”在这里指的是问题的状态是随时间（或某种形式的阶段）变化的，因此我们需要“动态地”制定计划或策略来求解问题。这种决策不是一下就出来的，而是一步步(multistage)积累出来。换句话说我们需要一个决策，但这个决策太大了，我们做不了，所以需要把他拆分到我们可以简单做出决策的状态，然后从这些状态开始，慢慢的“动态地”演进到最终的决策。


在Bellman的自传中他是这样描述的（英文机翻结果，稍作调整和补充）：
一个有趣的问题是，“动态规划这个名字是怎么来的？”。20世纪50年代对于数学研究来说并不是好年头。华盛顿有个很有趣的人，名叫威尔逊。他是国防部长，而且他实际上对“研究”这个词有一种病态的恐惧和厌恶。我这么说并不是轻率的；我是确切地使用这个词。他的脸会发红，如果他在场时有人提到“研究”这个词，他会暴怒。你可以想象他对“数学”这个词的感受。兰德公司受雇于空军，而空军实质上是由威尔逊掌管的。因此，我觉得我必须做点什么来保护威尔逊和空军，让他们不知道我在兰德公司里实际上在做数学研究。我能选择什么标题，什么名字呢？首先我对计划、决策、思考（ planning， decision making，thinking）感兴趣。但是出于各种原因，“计划”（planning）并不是一个好词。因此我决定使用“规划”（programming，主要用作名词、动词，作名词时译为“程式设计，程序编排；节目制作”，作动词时译为“编写程序；设计程式（program的ing形式））这个词。我想传达的理念是这是动态（dynamic）的，这是多阶段（multistage）的，这是随时间变化（time-varying）的——我想，让我们一箭双雕吧。让我们选一个在古典物理意义上有绝对精确含义的词，即“动态”。它还有一个非常有趣的属性作为形容词，那就是不可能用“动态”这个词来表示贬义。试着想想有没有可能给它一个贬义的组合。这是不可能的。因此，我认为动态规划是一个很好的名字。这是一个连国会议员都无法反对的东西。所以我用它作为我活动的掩护。

shaowu459

可使用动态规划解决的问题的特征


动态规划是一种解决最优化、搜索和计数问题的通用技术，这些问题都可以被分解为多个子问题。要应用动态规划，问题就必须具备以下两个属性：


1）最优子结构（Optimal substructure）：如果大小为n的问题的最优解可以由大小小于n的问题的同一实例的最优解推导出，则该问题具有最优子结构。将原有问题化分为一个个子问题，即为子结构。而对于每一个子问题，其最优值均由「更小规模的子问题的最优值」推导而来，即为最优子结构。问题的最优解是由相关子问题的最优解组合而成，且这些子问题都可以独立求解。也就是说一个问题的最优解包含其子问题的最优解，进而可以理解为，后面阶段的状态可以通过前面阶段的状态推导出来。


2）重叠子问题（Overlapping subproblems）：对同一个问题使用不同的决策序列，当到达某个相同的阶段时，可能会产生重复的状态。因此，如果不使用动态规划来解决这些重叠的子问题，就意味着在解题过程中可能会重复求解某些子问题。在动态规划中，每个子问题只需求解一次，并将结果保存起来。这样，下次出现相同子问题的时候就无需重新计算，只要查找到先前计算过的解即可，从而节省计算时间。

shaowu459

使用动态规划解决问题的思路


动态规划解决问题主要分为两个核心部分，一是确定「DP 状态」，二是确定「DP 转移方程」。


1、「DP 状态」设置之前，需要将原有问题划分为一个个子问题，且需要确保子问题的最优值由「更小规模子问题的最优值」推出，此时子问题的最优值即为「DP 状态」的定义。
2、有了「DP 状态」之后，我们只需要用「分类讨论」的思想来枚举所有小状态向大状态转移的可能性即可推出「DP 转移方程」。


在完成上述分析步骤之后，真正使用代码或函数公式实现动态规划求解过程时，还需要关注【边界值】的处理。

shaowu459

前面主要是一些概念性描述，下面我们用一个简单的例子来说明一下DP的思想。

问题：给定一个包含数字的数组（用nums表示，下图中的黄色区域），要求数组中的最大值。



我们用i作为数组元素的下标，按照一般编程中的规范，这个下标是从0开始。我们可以设定一个值dp来代表截止到第i个元素时数组中的最大值，然后我们从左到右遍历数组中的每一个元素。

从左到右遍历数组nums：

当i=0时，因为只有这一个数字，所以dp[0]=nums[0]=4，意为截止到下标i=0时，数组中元素的最大值是4。
当i=1时，dp[1]等于什么呢？因为dp[0]已存储了截止到下标i=0时的最大值，所以dp[1]只需要比较nums[1]和dp[0]的大小，取其中较大者即可。也即dp[1]=max(nums[1]，dp[0])=max(9,4)=9。
当i=2时，同样道理，dp[2]=max(nums[2]，dp[1])=max(4,9)=9。
后面以此类推，也即截止到下标i的最大值等于nums和dp[i-1]中的较大者。

从上面的分析中，我们可以总结在给定数组中取最大值的思路：如果只有一个元素，那最大值就是它（也就是初始边界值）；再增加一个元素，需要拿这个数和当下最大的数去比，其中较大的那个就是新的最大数，递推关系就是：dp=max(nums,dp[i-1])，也就是转移状态方程。这就是典型dp的思想，简单不准确概况就是“找规律”。

shaowu459

上面找数组中最大值的例子中，因为到每个下标i只有一个值或状态（截止到下标i时的最大值），所以可以使用dp来表示，dp的值会依赖截止到下标i-1时的值，这个值可以用dp[i-1]表示，同理还会有dp[i-2]、dp[i-3]……等。

对应的，如果根据需要设定到下标i时的值或状态有多个，可以用下面的方式来表示，也即在下标i时有[1]和[2]两种状态：
dp[1]
dp[2]
之前的状态可以用dp[i-1][1]、dp[i-1][2]和dp[i-3][1]、dp[i-3][2]等来表示。

还有些情况更复杂，例如一个二维的矩阵，需要使用i和j两个值来确定，可以用dp[i,j]表示。当下标为i-1并且j不变时，可以用dp[i-1,j]表示，同理，有dp[i-1,j-1]、dp[i,j-1]等状态表示方式。

shaowu459

使用DP来解决的问题相当广泛，例如一维DP有上台阶、最长递增子序列等，二维DP有最小路径和、最长公共子序列、背包问题等。

在使用代码或公式来实现DP的时候，是不是一定要把下标i之前所有的子问题的解全部存储下来呢？其实有时候并不一定需要。

如果通过分析，找到类似dp=max(dp[i-1],nums)或dp=dp[i-1]+dp[i-2]这种转移状态方程，你会发现当前的状态只和当前遍历的数组元素和前一个或前两个状态相关，这样，我们就不需要维持一个完整的数组存储i之前所有子问题的解，只需要使用一个临时变量或使用一个数组滚动存储i之前的特定状态值即可，这样就能减少运算，提高效率。

shaowu459

动态规划和贪心算法的区别

动态规划和贪心算法是两种不同的算法策略，它们在解决问题的方式、适用的场景以及算法复杂度上有显著的差异。以下是两种算法策略的区别：
1）解决问题的方式不同。动态规划通常用于解决将大问题分解为重叠子问题的情况，这些子问题可以复用解决方案。动态规划通过保存并重复使用子问题的解来构建全局最优解；贪心算法适用于做出当前最优选择能导致全局最优解的问题，它每步都选择局部最优解，不考虑未来后果，也不回溯已做决策。贪心可走树的从上到下的一枝，动态规划能遍历整棵树，有点穷举的意思。

2）算法复杂度不同。动态规划通常需要更多的计算和存储空间，因为它需要保存大量的中间结果；贪心算法通常更简单快速，因为它不需要保存中间结果，且经常以线性时间复杂度运行。
3）适用的场景不同。动态规划适用于有重叠子问题的情况，且适合用子问题的最优解来构建全局最优解的问题；贪心算法适用于问题可以分解为多个阶段，且每阶段的决策只依赖于当前状态，而不是未来的状态的问题。


需要注意的是，贪心算法和动态规划并不是互斥的，有些问题可以同时使用这两种算法进行求解。在某些情况下，贪心算法可以作为动态规划算法的一部分，用于优化算法的效率。

shaowu459

动态规划和递归的区别

递归和动态规划的关系是**动态规划经常使用递归作为实现手段**，但它们在概念上有所区别。动态规划是一种算法设计策略，用于解决具有重叠子问题和最优子结构特性的问题。它通过将问题分解为更小的子问题，并存储这些子问题的解来避免重复计算，从而提高效率。而递归是一种编程技巧，指的是函数直接或间接地调用自身来实现算法逻辑。动态规划通常有两种实现方式：自顶向下（top-down，即递归）和自底向上（bottom-up，非递归）。在这种意义上，递归可以视为动态规划的一种实现方法。

递归和动态规划的区别主要体现在**重复子问题的处理、存储结构、实现方式**等，具体如下：
1）**重复子问题的处理**：动态规划通过存储子问题的解来避免重复计算，而普通递归可能多次计算相同的子问题，导致效率低下。如下图，递归中会多次计算f(3)和f(2)。

2）**存储结构**：动态规划通常需要一个额外的存储结构来保存中间结果，而递归则不需要这样的结构，因为它天然地利用了系统栈。
3）**实现方式**：虽然递归可以用来实现动态规划，但并非所有递归算法都是动态规划。动态规划特指那些能够通过存储中间结果优化的递归算法。

总之，在实际应用中选择动态规划还是递归，取决于问题的特点以及是否需要优化性能。如果一个问题存在大量重复的子问题，那么采用动态规划将是更好的选择。如果重复计算不多，或者对空间有限制，可以考虑用递归。

shaowu459

例题1：
有n级台阶，每次只能上1或2级台阶，问从地面开始上到第n级台阶共有多少种上法。


下面我们最开始来分析一下，如何推理出转移状态方程。
当要上到第1级台阶时，只有一种走法，从地面上一级台阶。



当要上到第2级台阶时，有两种走法，一种是一次性上到第2级台阶，一种是每次走一级台阶。


当要上到第3级台阶时一共有几种走法呢？因为每次能上1级或2级，所以到第3级台阶可能是从第1级台阶迈两级台阶而来，也可能是从第2级台阶迈一级台阶而来。所以，上到第3级台阶的走法=上到第1级的走法+上到2级的走法，如果使用dp来表示上到第i级台阶的走法，可以写成dp[3]=dp[1]+dp[2]。


当要上到第4级台阶时道理一样，dp[4]=dp[2]+dp[3]，后面可以以此类推，规律是：上到第i个台阶时的走法=上到第i-2个台阶的走法+上到第i-1个台阶的走法，因此可以推出转移状态方程：dp=dp[i-2]+dp[i-1]。


在具体使用公式解决时（5级台阶为例），我们可以将第1级和第2级的走法作为初始值，也即{1;2}：

1. =MAX(REDUCE({1;2},SEQUENCE(5-2),LAMBDA(x,y,VSTACK(x,SUM(TAKE(x,-2))))))

复制代码

上述公式中SEQUENCE里的5是台阶总数，-2是减去已放入初始值的前两个台阶的走法。TAKE函数每次取x中的最后两行求和作为到第i级台阶时的走法，堆叠在x下方。当然，也可以改变堆叠方式：

1. =@REDUCE({2;1},SEQUENCE(5-2),LAMBDA(x,y,VSTACK(SUM(TAKE(x,2)),x)))

复制代码

前面的公式适用于2级以上台阶的情况，也可以在写DP时考虑作出虚拟的初始值来适应从第一级台阶开始的情况，例如：

1. =@REDUCE({1;0},SEQUENCE(5),LAMBDA(x,y,VSTACK(SUM(TAKE(x,2)),x)))

复制代码