本文是算法ABC笔记中的第一篇。是为了记录本人对b站up主“喂你脚下有坑”所发布的《算法ABC》有关视频的个人思考以及扩展相关题目笔记。
「笔记」对应的是视频以及博客笔记。「扩展」对应笔记相关的知识的个人思考以及扩展题目的记录。
[TOC]
基本术语
学习知识要统一术语，目的是加快认知，并且减少因为对词汇定义不同产生认知差异。
- 动态规划：运筹学中的一个分支，是求解决策过程最优化的数学方法。
- 阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段。
- 状态：状态表示每个阶段开始面临的自然状况或客观条件。
- 决策（转移）：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择称为决策。
- 策略：每阶段都做一个决策，一系列决策的集合。
- 边界：初始集合。
先理清楚逻辑再写代码！
最开始要做的是动态规划的状态设计，其中有两步：阶段划分与状态设计。因为阶段划分与状态设计这两部分关系非常紧密，所以我们将它们放在一起思考，统称为状态设计。
简单来说我们把原问题分成若干个不相交的部分，阶段代表了这些若干个不相交的部分，同时阶段需要一些信息来描述阶段中不同的情况。不同的情况就是状态，刻画情况的信息就是状态的表示。
这么看，阶段和状态没什么区别，都是用来描述问题的不同情况的。于是我们需要决策（转移）的出现。决策，对应动态规划中的状态的转移，一个决策可以让我们从一个阶段中的一个状态演变到另一个不同阶段的状态中去，如果将阶段中的状态看成是点，决策是点与点之间的有向边，阶段中的状态和决策就组成一个DAG（有想无环图）。这也保证了动态规划问题的优秀复杂度，即同一个状态不会直接间接更新自己。（意思就是在一次判断中不会出现两次同样的情况，这样会导致无限循环。）
再说明一次策略，策略是一些列决策的集合。
边界就是集合，字面意思，问题中易得的答案状态，我们称之为初始状态，动态规划的过程一般从初始状态开始向后进行。
如果觉得抽象，看看wnjxyk老师举的生动的例子！WNJXYK老师的博客
我们可以从这个例子中更透彻地了解动态规划、阶段、状态、决策、策略和边界的意义。
动态规划问题性质
接下来，我们通过一个经典例子了解三个有关动态规划状态需要满足的性质。
- 最优子结构：一个最优化策略的子策略总是最优的，反过来，我们可以通过最优子策略，推出最优策略。
- 无后效性：当我们通过一系列策略到达了某一阶段的某一状态时，下一步决策不受之前的一系列策略影响，仅由当前状态决定。
- 子问题重叠：算法计算的过程中会反复地求解相同的一定量的子问题，而不是不断生成没有见过的新问题。也就是说子问题空间不大，或是状态空间不大，我们可以通过存储状态的答案加快计算速度。
举例为数塔：有如下所示的数塔，要求从顶走到底，若每一步只能走到相邻节点，则经过的节点的数字之和最大是多少？
数塔问题例子
首先考虑上一节所说的状态标识与转移，我们先找一组符合动态规划要求性质的表示与转移。
- 阶段：数塔的每一层就是一个阶段，转移的时候，从上一层向下一层转移。
- 状态：位于数塔每一层的那个节点就是状态，因为每一步只能走到相邻的节点，所以状态决定了能够向下一阶段的哪些状态转移。
- 状态转移：由题目中 每一步只能走到相邻的结点 得到，状态转移就是上一层节点向下一层相邻节点转移。
- 初始状态：由题目中得到，数塔顶部节点。
由状态和阶段我们可以得到：
- 状态表示：dp[i][j]表示位于第i层第j个元素的最大数字之和
- 状态转移即为dp[i][j]=max（dp[i-1][j-1],dp[i-1][j]）+v[i][j]
- 初始状态为dp[1][1]=9。
当我们在状态（i,j）即第i行第j列，我们只能从状态 (i-1,j-1)(i−1,j−1) 与状态 (i-1,j)(i−1,j) 走过来，(i,j)(i,j) 的最优决策一定能由它的两个子决策 (i-1,j-1)(i−1,j−1) 与 (i-1,j)(i−1,j) 推导出来，这就满足了优父亦优最优子结构性质。反应到状态转移方程中，我们就可以放心写出
- dp[i][j]=max(dp[i−1][j−1],dp[i−1][j])+v[i][j]。
- 最优子结构性质
因为我们需要的是结果，并不关心具体决策序列，所以数组中直接存储最优决策数字即可。
状态表示为（i，j）的时候，我们只考虑状态是从（i-1，j-1）还是（i-1，j）走过来，不考虑之前如何走到（i-1，j-1）还是（i-1，j），这就是结果的结果不是我的结果无后效性。个人感觉后效性和状态表示是密切相关的，事实也是如此。当我们发现我们的状态表示存在后效性，很大可能性就是有没考虑到的东西没有加入状态表示，当我们加入这些东西，后效性也就自然而然消除了。
- 无后效性
最后说子问题，这个问题的子问题只有种，数量为
级别的。
- 子问题重叠
至此我们对应最优子结构，无后效性，子问题重叠的三个有关动态规划状态需要满足的性质都达成了。
错误案例
最后我们看两种反面教材以及一个拓展结束本章笔记。
-
无后效性缺失
状态表示为dp[i]表示位于第i层的最大数字和，这种状态表示具有后效性。 -
不存在子问题重叠
状态表示为dp[a][b][c][d][e]第一层走节点为a，第二层走节点为b.......，第五层走节点为e的路径下的最大数字和。状态唯一的表示了所有走塔的行走情况，不存在子问题重叠。但我们要求的是求最大值而不是相对应的路线，不需要这些数据！且子问题数量增加为，无法接受。
3.拓展（不符合最优子结构）
一般来说，求最大值、最小值这种目标式单调的问题，最优子结构性质是符合的，求什么绝对值、标准差、差值之类的，前期结果雪崩，到最后一步力挽狂澜的问题，最优子结构不能符合。
详细例子看喂你脚下有坑老师本节对应博客
动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
以上是力扣上动态规划词条。
网友评论