动态规划-入门（记忆搜索与逆序递推）

本篇博文旨在进行动态规划的入门，介绍基础思想。动态规划是十分基础的思想，但其依旧有一定的难度，特别是对于像我这种非计算机专业且无竞赛经验的爱好者。

动态规划简介

动态规划本身并无实际意义，它更像一种思想与手段以解决问题。如果一个问题可以被分解为若干子问题，且子问题又可解决主问题，我应该考虑动态规划。

动态规划有四个关键： 1. 状态 2. 状态转移 3. 最优子结构 4. 重叠子问题

引子

我们以力扣上最简单的动态规划为例（70.爬楼梯）。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶

我先不考虑动态规划，以最简单朴素的思想去思考。我可以构建一个二叉树，左右子节点分别代表爬 1 或 2 个台阶。我以爬 4 阶为例，二叉树如图。

如果了解回溯法，马上反应过来这种二叉树可以使用回溯法生成。实际上回溯法确实和动态规划有些交际，就我目前观察，只要求判断对错、输出个数常见动态规划；要求输出过程的只能回溯法生成了。

就算你不知道回溯法，相信你也能看出这幅图有很多地方是重复的。比如 1 节点的左子树不就是 2 节点的子树吗？相似的地方还有很多，这就是重叠子问题。在遍历时有大量的计算是重复的，动态规划实际上就是要解决重叠子问题。

为了解决重叠子问题，一般有两类： 1. 记忆化搜索 2. 逆向递推

记忆化搜索

记忆化搜索很简单，比如你先生成 1 节点的子树，然后去看看 1 的左子树 2 节点，然后先去 3 节点之后又去 4 节点。完成 1 节点的子树后，你实际上已经生成过一遍 2,3,4 节点的子树了，记下来，下次要查看 2,3,4 节点就直接调用记录即可，不用重新生成。

那么，如何根据已经储存的节点数据得到新的节点数据呢？这就是状态和状态转移方程的工作。

我设 node(x) 表示 x 台阶到 n 台阶的不同方法总数，即题目所求为 node(1)。这就是状态。

1 台阶能到达 2,3 台阶，因此它的状态为 2,3 状态相加。有 node(1)=node(2)+node(3)，我将其扩展到一般状态 node(x)=node(x+1)+node(x+2)，这就是状态转移方程。

现在我完成了动态规划的所有问题，就剩编码实现了。一个简单 C++ 的实现如下

int node[100];
memset(node,0,sizeof(node));
int n;
int dp(int i){
  if(i>=n) return 1;
  if(node[i]>0) return node[i];
  return node[i]+=dp(i+1)+dp(i+2);
}

一行一行看，int node[100]定义了一个足够大的数组用以储存每一个节点的状态，node[1] 就是 1 台阶状态...

memset(node,0,sizeof(node)) 将 node 数组全部初始化为 0 ，这便是动态规划的初始化。

int n储存目标台阶数。

dp函数是动态规划的关键，if(i>=n) return 1判断当前试图计算的台阶是否已经超过目标，即动态规划的边界条件。

if(node[i]>0) return node[i]如果希望计算的台阶状态已经计算过了，直接返回结果，实现记忆化。

return node[i]+=dp(i+1)+dp(i+2)先根据状态转移方程计算当前台阶状态，这里利用了 c++ 赋值语句本身返回结果的特性少写了一行代码。

逆序递推

记忆化搜索虽能解决问题，但不停递归比较慢，逆序搜索可以使用循环解决问题。

经过上面的分析，我的目标是解决递推时出现的大量重复计算。观察状态转移方程node(x)=node(x+1)+node(x+2)和二叉树，可以发现要计算一个节点就必须先求下一个节点，如果我直接从后往前计算，我也能防止重复计算。

下面是一个简单的 c++ 实现

int n;
int dp(int i) {
  int node[n+1];
  memset(node,0,sizeof(node));
  node[n]=1;
  node[n-1]=2;
  for(int i=n-2;i>=1;i--){
    node[i]=node[i+1]+node[i+2];
  }
  return node[1];
}

依旧一行一行看，int n储存目标台阶数。

int node[n+1]定义了一个数组用以储存每一个节点的状态，这里使用了 C 语言的可选功能可变数组，因此 g++ 和 clang++ 可以编译通过但 msvc 不行（力扣使用 clang++ 因此可以通过）。可以改为int node[100]以符合标准 C++。

memset(node,0,sizeof(node)) 将 node 数组全部初始化为 0 。 node[n]=1 与 node[n-1]=2 分别表示最后一个台阶的状态为 1，倒数第二个台阶状态为 2。这三条代码完成了动态规划的初始化。

一个从后往前的循环，利用状态转移方程完美的完成了逆序递推。

最后返回结果。

结语

至此，动态规划的基础算是打下了，但要完成动态规划的题目还要掌握一些数据结构和常见动态规划模型（状态转移方程）。我在最开始学习算法时就碰见了动态规划，那时我只自学了一些 c++ 和 python 的简单语法，数据结构和算法是两眼一抹黑。看见 memset 函数我都蒙了，因此动态规划很长一段时间是我的噩梦，现在我总算解决了。（笑