【知识点】一文讲清动态规划的实质
一文讲清动态规划的实质
动态规划 Dynamic Programming (DP) 是算法范畴的中心思维之一，却一起也是让许多学习者感到扎手的难点之一。动态规划的难点在于它不是简略的数学推导，也不单纯检测人们的程序规划才能，而更像是一种从思维办法到问题建模的一次深入练习。
本文将从动态规划的界说动身，深入探讨动态规划的实质、运用场景、中心特色、解题思路以及怎么逐渐进步处理动态规划问题的才能。
动态规划的界说和运用：将大问题分化成许多小问题
动态规划的中心思维能够被归纳为一句话：将一个杂乱的问题分化成多个简略的子问题，并经过保存子问题的解来防止重复核算，然后进步求解功率。
换句话说，动态规划适用于处理以下两类问题：
- 最优子结构问题：所谓的最优子结构问题，便是一个最优解能够经过其子问题的最优解而构成。
- 子问题堆叠问题：多个子问题在递归的进程中会重复呈现，而且会被屡次核算到。
E.g. 01 - 斐波那契数列 \(\mathrm{I}\)
咱们都知道斐波那契的通项公式是 \(F(n) = F(n-1) + F(n-2)\)。以核算斐波那契数列的第五项 \(F(5)\) 为例，很显然，\(F(5)\) 便是咱们需求求解的大问题，而这个大问题能够被逐渐分化为两个小问题，即 \(F(4)\) 和 \(F(3)\) 。只需咱们知道了 \(F(4)\) 和 \(F(3)\)，那么咱们就能够将这两项相加来得到终究的成果。这个便是最优子结构的表现。
那什么时分会呈现子问题堆叠呢？咱们无妨用代码来完成斐波那契数列：
// 函数的界说
int fib(int n){
// 依据斐波那契数列的界说：
// 该数列的第零项为0，榜首项为1
if (n == 0) return 0;
if (n == 1) return 1;
// 依据式子写出递归代码。
return fib(n-1) + fib(n-2);
}
// 履行函数
cout << fib(5) << endl;
这是一个很简略的递归算法。经过模仿递归算法咱们能够画出一个递归图：
经过调查这个图能够发现，在核算 \(F(5)\) 的时分，\(F(3)\) 被 \(F(5)\) 调用过一次，一起又被 \(F(4)\) 调用一次。相同地，\(F(2)\) 被 \(F(3)\) 调用了两次，被 \(F(4)\) 也调用了一次。咱们能够发现这个图中有许多的重复核算，这会大大糟蹋程序的运转时刻。可是这便是所谓的子问题堆叠问题。
针对这类型的问题，有什么处理计划呢？最直接的办法便是把现已核算过的答案保存下来，下次再调用的时分直接获取成果就能够了，这种办法便是咱们常说的“回忆化”。回忆化查找的代码如下：
memset(memo, -1, sizeof memo);
int fib(int n) {
// 假如现已核算过，直接回来成果
if (memo[n] != -1) return memo[n];
// 不然，递归核算，并将成果存储在 memo 中
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
这个代码与一般斐波那契数列仅有的差异便是添加一个 memo 数组，判别某一个值是否现已被核算过。假如现已被核算过就直接回来，而不需求继续递归来耗费时刻。
而另一种处理办法便是“递推“，咱们能够从小到大，先核算 \(F(0)\) 和 \(F(1)\) 并把答案保存下来，核算 \(F(2)\) 的时分就能够马上经过将 \(F(0)\) 和 \(F(1)\) 相加得到成果。这种递推的做法便是所谓的动态规划思维。而这么做的代码也愈加简练：
int fib[10005];
fib[0] = 0, fib[1] = 1;
for (int i=2; i<=n; i++)
fib[i] = fib[i-1] + fib[i-2]
cout << f[n] << endl;
因而，动态规划的中心思维便是经过 记载 和 重用 子问题的解，防止重复核算，然后进步求解功率。动态规划是一种典型的 拿空间换时刻 的思维（究竟现在的社会，时刻本钱比空间本钱高太多了）。
动态规划与分治思维的首要差异便是分治算法首要运用于子问题不堆叠的问题，而针对子问题堆叠的问题，动态规划是一个更好的挑选。
动态规划的性质
动态规划的三个根本性质是：最优子结构、子问题堆叠 以及 无后效性。前两个性质现已在榜首部分提及过了，本部分首要解说无后效性。
无后效性，又称马尔可夫性，这意味着某阶段的状况一旦确认，就不承受该状况之后决议计划的影响。即，某状况今后的进程不会影响之前的状况，只与当时的状况有关。用一句话归纳便是“曩昔的工作不会影响未来，只重视当时的状况”。
除了无后效性，动态规划的另一个中心在于 最优性原理，即一个最优解包含其子问题的最优解。这一原理是由理查德·贝尔曼（Richard Bellman）提出。最优性原理是动态规划思维的理论柱石。
E.g. 02 - 斐波那契数列 \(\mathrm{II}\)
回到本来斐波那契数列场景，当核算 \(F(5)\) 时，答案只依赖于当时状况 \(F(4)\) 和 \(F(3)\) 的值，与更早的前史状况无关。这便是为什么，咱们在核算 \(F(5)\) 的时分能够直接运用 \(F(3)\) 和 \(F(4)\) 之前被核算出来的成果相加得到答案，而不是从 \(F(1)\) 和 \(F(0)\) 开端从头核算。
与此一起，在具有无后效性的场景中，一旦某一个状况的值现已被核算下来并能够搬运到下一个状况时，这个状况将不会再被改动。换句话说，某状况今后的进程不会影响曾经核算出来的状况，只与当时的状况有关。
无后效性是防止重复核算子问题的前提条件。
动态规划和递归的相关
在看到这儿，你会发现动态规划和递归这两个思维有着异曲同工之妙。事实上，大多数的动态规划问题都能够运用回忆化查找（递归）来处理。动态规划和暴力递归的要害差异如下：
- 递归：经过函数自调用，将问题分化为子问题，直到到达根本情况。递归或许导致很多重复核算，功率较低。
- 动态规划：经过记载已处理的子问题的解，防止重复核算。动态规划一般选用自底向上的办法，功率更高。
因而广义而言。带有回忆化查找的递归算法也能够被称之为是动态规划。
处理动态规划问题的根本思路
处理动态规划问题的根本思路如下：
过程一：确认不同的阶段和变量
依据标题的特性，咱们能够把一个问题拆解成小问题，将一个小问题拆分红一个个次小问题，以此类推。那么在这之中，每一个需求处理的问题就被称之为一个阶段（状况）。因而关于动态规划问题，榜首步需求做的便是测验怎么把大问题分化成许多个有相关的问题。一起，咱们需求找到每一个阶段之间都是经过什么变量相关起来的。在斐波那契数列问题中，变量便是斐波那契数列的项数。
过程二：确认状况搬运方程式
在动态规划中，咱们把每一个“阶段”称之为一个状况。例如，\(F(5)\) 就能够被称之为是一个状况。咱们需求搞清楚大问题的状况和小问题的状况之间的相关。
在斐波那契数列中，这个相关便是：序列的第 \(i\) 项为序列的第 \(i-1\) 和第 \(i-2\) 项的和。用数学表明便是 \(F(n) = F(n-1) + F(n-2)\)。在其他的比如中（愈加实际一点的），状况搬运方程往往与决议计划有着密不可分的联系（比如请参阅【E.g. 03 - 数楼梯】）。
在规划状况搬运方程式时，你需求包含一切或许涉及到的变量。以保证能在后续的程序完成过程中保存一切的或许性。
过程三：确认初始状况和边界条件
将问题分化成不能够再被分化的问题，这些问题被称之为最小问题。关于每一个最小问题，应当能够做到直接得出答案，而不需求经过核算。
例如在斐波那契数列中，所谓的最小问题便是 \(F(0)\) 和 \(F(1)\) 的值。这两个值的核算不需求依赖于任何的递推式子，而是依据界说或许逻辑直接给出的。
因而咱们需求设置 \(F(0)\) 和 \(F(1)\) 的初始值，而且将这两个状况设置成边界条件。
E.g. 03 - 数楼梯
标题描绘
一个楼梯有 \(N\) 级台阶，上楼能够一步上一阶，也能够一步上二阶。请你编写一个程序，核算走到第 \(N\) 级台阶共有多少种不同的走法。
解题思路
这是一道动态规划的经典例题，关于初学者而言或许对这道标题没有任何的条理，让咱们依照【处理动态规划问题的根本思路】一步一步来处理这道题。
首要确认不同的阶段，关于这道题而言，很显然不同的的阶段便是走到不同阶数的计划数，而当时楼梯的阶层便是仅有的变量。每上一层楼梯，这个变量就会添加。咱们无妨界说 \(dp_i\) 表明走到第 \(i\) 阶楼梯的计划数。
接下来确认变量和状况搬运方程，在这个场景中，咱们考虑每一个状况之间的相关。假定咱们要知道走到第十级台阶的计划数，可是咱们知道想要走到第十级台阶，咱们只要两个或许性（决议计划）：
- 从第九级台阶迈一步走到第十级台阶。
- 从第八级台阶迈两步走到第十级台阶。
除了这两种办法，咱们没有挑选。换句话说，走到某一级台阶的计划数只跟走到这之前一级和之前两级台阶的计划数有联系（无后效性），而且计划数便是这两种或许性相加的和（逻辑上也是这姿态的）。用一个更广泛的式子来描绘便是：
