DP笔记(1)：动态规划概念剖析与分类讲解
Author：zhoulujun Date：
动态规划(dynamic programming)
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。
20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
动态规划的定义
动态规划的英文名称为：dynamic programming，接下来看下《Introduction to algorithms》对动态规划的定义：
A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.
动态规划算法解决每一个子问题，仅一次，然后保存子问题的结果到内存表中，以此来避免对子问题的重复计算。
两种实现方法
top-down with memoization 使用内存自顶向下。保存子问题的结果，之后在求解某个子问题时，若其用到的某个子问题且已经保存了结果，直接返回。
bottom-up method 在求某个子问题时，会依赖已经求出的更小的子问题的解。
动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。
动态规划的基本思想是：
问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，再构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。
动态规划与暴力、回溯算法的区别
所有动态规划问题都能通过暴力方法解决！是的，所有最优解问题都可以通过暴力方法尝试（以及回溯算法），最终找出最优的那个。
暴力算法几乎可以解决一切问题。回溯算法的特点是，通过暴力尝试不同分支，最终选择结果最优的线路。
而动态规划也有分支概念，但不用把每条分支尝试到终点，而是在走到分叉路口时，可以直接根据前面各分支的表现，直接推导出下一步的最优解！然而无论是直接推导，还是前面各分支判断，都是有条件的。动态规划可解问题需同时满足以下三个特点：
存在最优子结构。
存在重复子问题。
无后效性。
存在最优子结构
即子问题的最优解可以推导出全局最优解。
什么是子问题？比如寻路算法中，走完前几步就是相对于走完全程的子问题，必须保证走完全程的最短路径可以通过走完前几步推导出来，才可以用动态规划。
不要小看这第一条，动态规划就难在这里，你到底如何将最优子结构与全局最优解建立上关系？
对于爬楼梯问题，由于每层台阶都是由前面台阶爬上来的，因此必然存在一个线性关系推导。
如果变成二维平面寻路呢？那么就升级为二维问题，存在两个变量 i,j 与上一步之间关系了。
如果是背包问题，同时存在物品数量 i、物品重量 j 和物品质量 k 三个变量呢？那就升级为三位问题，需要寻找三个之间的关系。
依此类推，复杂度可以上升到 N 维，维度越高思考的复杂度就越高，空间复杂度就越需要优化。
存在重复子问题
即同一个子问题在不同场景下存在重复计算。
比如寻路算法中，同样两条路线的计算中，有一段路线是公共的，是计算的必经之路，那么只算一次就好了，当计算下一条路时，遇到这个子路，直接拿第一次计算的缓存即可。典型例子是斐波那契数列，对于 f(3) 与 f(4)，都要计算 f(1) 与 f(2)，因为 f(3) = f(2) + f(1)，而 f(4) = f(3) + f(2) = f(2) + f(1) + f(2)。
这个是动态规划与暴力解法的关键区别，动态规划之所以性能高，是因为 不会对重复子问题进行重复计算，算法上一般通过缓存计算结果或者自底向上迭代的方式解决，但核心是这个场景要存在重复子问题。
当你觉得暴力解法可能很傻，存在大量重复计算时，就要想想是哪里存在重复子问题，是否可以用动态规划解决了。
无后效性
即前面的选择不会影响后面的游戏规则。
寻路算法中，不会因为前面走了 B 路线而对后面路线产生影响。斐波那契数列因为第 N 项与前面的项是确定关联，没有选择一说，所以也不存在后效性问题。
什么场景存在后效性呢？比如你的人生是否能通过动态规划求最优解？其实是不行的，因为你今天的选择可能影响未来人生轨迹，比如你选择了计算机这个职业，会直接影响到工作的领域，接触到的人，后面的人生路线因此就完全变了，所以根本无法与选择了土木工程的你进行比较，因为人生赛道都变了。
有同学可能觉得这样局限是不是很大？其实不然，无后效性的问题仍然很多，比如背包放哪件物品、当前走哪条路线、用了哪些零钱，都不会影响整个背包大小、整张地图的地形、以及你最重要付款的金额。
最优子结构详解
我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。
我给你提出的这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
你看，这么简单的问题都有最优子结构性质，只是因为显然没有重叠子问题，所以我们简单地求最值肯定用不出动态规划。
再举个例子：假设你们学校有 10 个班，你已知每个班的最大分数差（最高分和最低分的差值）。那么现在我让你计算全校学生中的最大分数差，你会不会算？可以想办法算，但是肯定不能通过已知的这 10 个班的最大分数差推到出来。因为这 10 个班的最大分数差不一定就包含全校学生的最大分数差，比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差。
这次我给你提出的问题就不符合最优子结构，因为你没办通过每个班的最优值推出全校的最优值，没办法通过子问题的最优值推出规模更大的问题的最优值。前文 动态规划详解 说过，想满足最优子结，子问题之间必须互相独立。全校的最大分数差可能出现在两个班之间，显然子问题不独立，所以这个问题本身不符合最优子结构。
那么遇到这种最优子结构失效情况，怎么办？策略是：改造问题。
改造问题，也就是把问题等价转化：最大分数差，不就等价于最高分数和最低分数的差么，那不就是要求最高和最低分数么，不就是我们讨论的第一个问题么，不就具有最优子结构了么？那现在改变思路，借助最优子结构解决最值问题，再回过头解决最大分数差问题，是不是就高效多了？
最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；但反过来，最优子结构性质作为动态规划问题的必要条件，一定是让你求最值的，以后碰到那种恶心人的最值题，思路往动态规划想就对了，这就是套路。
无后效性和最优子结构是动态规划的必要条件，但不是充分条件。即一些不满足无后效性或最优子结构特征，但仍然可以使用动态规划来解决的示例。如不满足无后效性：旅游问题、调度问题；不满足最优子结构：背包问题、树木分割问题。
解法套路 - 状态转移方程
解决动态规划问题的核心就是写出状态转移方程，所谓状态转移，即通过某些之前步骤推导出未来步骤。
状态转移方程一般写为 dp(i) = 一系列 dp(j) 的计算，其中 j < i。
其中 i 与 dp(i) 的含义很重要，一般 dp(i) 直接代表题目的答案，i 就有技巧了。比如斐波那契数列，dp(i) 表示的答案就是最终结果，i 表示下标，由于斐波那契数列直接把状态转移方程告诉你了 f(x) = f(x-1) + f(x-2)，那么根本连推导都不必了。
对于复杂问题，难在如何定义 i 的含义，以及下一步状态如何通过之前状态推导。 这个做多了题目就有体会，如果没有，那即便再如何解释也难以说明，所以后面还是直接看例子吧。
https://labuladong.online/algo/essential-technique/dynamic-programming-framework/
虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，需要你熟练掌握递归思维，只有列出正确的「状态转移方程」，才能正确地穷举。而且，你需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。
动态规划不就是从最简单的 base case 往后推导吗，可以想象成一个链式反应，不断以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。
找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。这也是套路，经常刷题的朋友应该能体会。
动态规划的解题步骤
定义子问题
子问题是和原问题相似，但规模较小的问题。第一步就是缩小规模，利用小规模子问题刻画其结构特征。
划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
说明：创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定
注意：子问题的解一旦求出就会被保存，所以每个子问题只需求解一次。
写出子问题的递推关系
找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。
确定一些初始状态（边界状态）的值
确定状态转移方程： 定义出什么是"状态"，以及如何从一个或多个"值"已知的 "状态"，求出另一个"状态"的"值"(递推型)。状态的迁移可以用递推公式表示，此递推公式也可被称作"状态转移方程"。
确定 DP 数组的计算顺序
在确定了子问题的递推关系之后，下一步就是依次计算出这些子问题了。一般地，动态规划有两种计算顺序：
自顶向下的、使用备忘录的递归方法
自底向上的、使用 dp 数组的循环方法。
不过在普通的动态规划题目中，99% 的情况我们都不需要用到备忘录方法，即自底向上的 dp 数组。
空间优化（可选）
目的：空间复杂度的较小。
在很多问题中，DP数组并非全部用上，很多情况下只使用一小部分或空间可重复利用，这给空间压缩带来可能。
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎
先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。
这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。
但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
15=1×11+4×1 （贪心策略使用了5张钞票）
15=3×5 （正确的策略，只用3张钞票）
为什么会这样呢？贪心策略错在了哪里？
鼠目寸光。
刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。
在这里我们发现，贪心是一种只考虑眼前情况的策略。
那么，现在我们怎样才能避免鼠目寸光呢？如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。
重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。
那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？
cost = f(4)+1 = 4+1 = 5，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。 依次类推，马上可以知道：如果我们用5来凑出15，cost就是f(10)+1=2+1 = 2 + 1 = 3
那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！
- 取11：cost=f(4)+1=4+1=5
- 取5： cost=f(10)+1=2+1=3
- 取1： cost=f(14)+1=4+1=5
显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！
这给了我们一个至关重要的启示—— f(n)只与 f(n−1),f(n−5),f(n−11)相关；更确切地说：
f(n)=min{f(n−1),f(n−5),f(n−11)}+1
这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。
动态规划理解起来还是比较困难，什么重叠子问题、动态转移方程，优化点等等等等，好好看着其他人的分享，每个理解了一部分，然后疯狂刷他几十道。算是基本可以佛挡杀佛了。
其实动态规划非常有必要掌握：
非常锻炼思维。动态规划是非常锻炼脑力的题目，虽然有套路，但每道题解法思路差异很大，作为思维练习非常合适。
非常实用。动态规划听起来很高级，但实际上思路和解决的问题都很常见。
动态规划用来解决一定条件下的最优解，比如：
自动寻路哪种走法最优？
背包装哪些物品空间利用率最大？
怎么用最少的硬币凑零钱？
动态规划的分类
态规划是一种解决复杂问题的算法，它通过将问题分解成更小的子问题，并存储子问题的解决方案来提高效率。动态规划的两个关键特征是：
重叠子问题：问题可以分解成多个相同的或相似的子问题。
最优子结构：一个问题的最优解可以由其子问题的最优解组合而成。
根据这两个特征，动态规划可以分为如下6大类，可以依次进行学习：线性动规、背包问题、递推型动态规划、区间动态规划、树形动规、状态压缩动态规划。
线性动态规划（Linear Dynamic Programming）：
这类动态规划主要解决线性序列相关的问题，例如字符串、数组等。
问题的解可以表示为一维数组或者矩阵，通常具有最优子结构和重叠子问题的性质。
线性动态规划通常是入门级别的动态规划类型，可以通过递推的方式求解。
剪绳子问题（LeetCode 343. Integer Break）
整数拆分（LeetCode 343. Integer Break）
比如最长公共上升子序列 (Longest Common Increasing Subsequence，LIS)，最长递增子序列 (Longest Increasing Subsequence，LIS) ，数字三角形，背包问题，邮局问题。这些题也可以衍生出难题，这里的难主要是状态难想，或者想出来的动态规划算法比最佳解答复杂度高。如经典的最长公共上升子序列 (Longest Common Increasing Subsequence)，实际上可以用O(N^2)的算法解出来；再如各种优化，比如LIS可以优化到O(NlgN)的时间。
背包问题（Knapsack Problem）：
问题涉及到物品装配的方式，要求达到最大价值或者最小成本，通常分为0-1背包、完全背包和多重背包等。
背包问题相对较为复杂，但是在理解了线性动态规划后，掌握背包问题通常不是很困难，因此排在第二位。
背包问题（0-1 Knapsack Problem）
完全背包问题（Complete Knapsack Problem）
多重背包问题（Multiple Knapsack Problem）
递推型动态规划（Recursive Dynamic Programming）：
问题的解可以通过递归地求解子问题得到，通常需要使用记忆化搜索或者递归优化来避免重复计算。
递推型动态规划虽然也是入门级别的，但是相对于线性动态规划来说，可能需要更深入的理解和思考。
区间动态规划（Interval Dynamic Programming）：
常用于处理序列型的问题，其中问题的解取决于序列中的某个区间。问题的解依赖于问题中的区间，通常需要考虑区间的起始和结束位置。
典型问题包括在序列中寻找最优的子区间，或者计算序列中所有子区间的最优解。
问题的解通常可以通过填表格的方式进行动态规划求解，每个表格表示某个区间的最优解。
它们的主要特点是用一个区间做状态，每个区间的最优解依赖于它的子区间。一般来说写成循环的话要先按照区间长度递增的顺序在最外层枚举。如果问题是线性的(如矩阵链乘、线状石子合并)很简单；如果是环状的(如环状石子合并，能量项链)，一般有两种处理方法：其一是将环展开成线性的(比如有N堆石子摆成一圈，那么就认为有2N堆石子摆在一条线上，其中第j堆和第N+j堆石子数目一样)，其二是设置状态时允许循环(比如用f[i][j]表示从第i堆石子开始，顺时针合并j堆石子所能得到的最大/小值)。
区域动态规划（Area Dynamic Programming）：
常用于处理二维或多维的网格型问题，其中问题的解取决于某个区域或者网格的状态。
区域动态规划涉及到二维网格、矩阵等区域结构。典型问题包括在网格中寻找某个区域的最优解，或者计算网格中所有区域的最优解。
问题的解通常可以通过填表格的方式进行动态规划求解，每个表格表示网格中某个区域的最优解。
最大子矩阵和（Maximum Submatrix Sum）
最大正方形子矩阵（Maximum Square Submatrix）
区间动态规划关注的是序列中的一段区间，而区域动态规划关注的是二维或多维网格中的某个区域。
树形动态规划（Tree Dynamic Programming）：
问题的解与树的结构有关，典型的是在树上进行DP的问题。
树的最大独立集（Maximum Independent Set in a Tree）
二叉树中的最长连续序列（Longest Consecutive Sequence in Binary Tree）
状态压缩动态规划（Bitmask Dynamic Programming）：
通常应用于某些组合问题，用二进制位表示状态。
这一类算法出现的时间并不太久，典型的题目就是铺砖问题。POJ上有很多类似地题目，就是给了若干种不同形状的瓷砖，问铺满一个房间有多少种方案。二十多年前这些题目被认为是搜索的典型题，技巧主要是构造沟壑是递归函数尽快遇到不满足条件的地方然后返回，也就是说剪枝。但现在的OIer和ACMer一般都用状态压缩动态规划来解，网上可以搜到很多例子，就不详细解释了。
参考文章：
https://algo.itcharge.cn/10.Dynamic-Programming/
动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结 https://cloud.tencent.com/developer/article/1692068
五大基本算法之动态规划算法 DP https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp
【DP-01】动态规划算法原理介绍 https://www.cnblogs.com/yifanrensheng/p/12940852.html
https://github.com/ascoders/weekly/blob/master/算法/198.精读《算法 - 动态规划》.md
https://www.bilibili.com/video/BV1AB4y1w7eT
转载本站文章《DP笔记(1)：动态规划概念剖析与分类讲解》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9109.html