浅谈动态规划算法

总阅读量次

关于动态规划(Dynamic Programming)算法，我在算法设计课上理解得并不是多么深刻。所以自己还是下来查找资料，多方对比学习，以期有所获。在这里谈一下心路历程与总结。

　　动态规划是运筹学中求解决策过程中的最优化数学方法。在计算机科学中，它也是一种程序算法设计技术。这就是基础科学在计算机科学中的一种应用。在这里我们只关注它作为算法设计技术的特性。

LV1-初识

　　一开始，课本上就扔出几个术语，最优子结构、重叠子问题，对于初学者来说的确是高深莫测，只有真的勇士才敢逆流而上，去一步一步剖析这些特性，最终能够领略它的独特风光。这里我们就逐个击破这些术语，揭开DP的面纱…

最优子结构

下面我们直接看经典的数塔问题:

从数塔顶部开始往下走，每次往下走只能选一个节点，一直到最底层，使走过的所有节点的数字之和最大，求这个最大和。假设顶部为第一层，以此类推。
数组$number[i][j]$表示数塔第i层左起第j个元素。

我们假定: $dp\[i\]\[j\]$表示从位置$(i,j)$到达数塔的最底层所经过路径的最大值。我们要得到该最大值，就必须得到分别从位置$(i+1,j+1)$和$(i,j+1)$这两个节点出发，到达最底层时，所经过的数字的最大值。此时，它们的关系为:

dp[i][j]=max(dp[i][j+1],dp[i+1][j+1])+number[i][j]

例如对于图中节点数字9

dp[1][1]=max(dp[2][1],dp[2][2])+9

这样我们得到的一般的等式就称为状态转移方程。

其中$dp[i][j]$表示一个状态，它的值总是来自于从子问题：$dp[i+1][j]$与$dp[i+1][j+1]$中选取一个较大值与当前节点数字相加，
之后对于节点$dp[i+1][j]$，它的值来自$dp[i+2][j]$与dp$[i+2][j+1]$中较大值与当前节点$number[i][j]$的和；$dp[i+1][j+1]$亦然。
这就是最优子结构性质，每一个问题都划分为两个子问题，然后在两个子问题中选择最优的(也就是所经过的数字之和最大)，得到母问题的最优解(当然是最优的)。

最终到了数塔最底层，此时已没有子问题，所以
假设数塔有n层，第n层有m个元素，
则$dp[n][j]=number[n][j]（1\leq j \leq m）$，这就称为递推边界。
从递推边界开始，根据状态转移方程，最终得到最优解$dp[1][1]$。
下面是C++代码:

#include<iostream>
#include<array>
#define ROW 4
#define COL 4
using namespace std;
int main()
{
  array<array<int, ROW+1>, COL+1> tower;
  array<array<int, ROW+1>, COL+1> dp;
  for(int i = 0; i < ROW; i++)
      tower[i].fill(0);
  for(int i = 1; i <= ROW; i++)
      for(int j = 1; j <= i; j++)
          cin >> tower[i][j];
  for(int i = 1; i <= ROW; i++)         // 递推边界
      dp[ROW][i] = tower[ROW][i];
  for(int i = ROW - 1; i >= 1; i--)
  {
      for(int j = 1; j <= i; j++)
      {
          dp[i][j] = max(dp[i + 1][j], dp[i +  1][j + 1]) + tower[i][j];  // 状态转移方程递推
      }
  }
  cout << dp[1][1] << endl;
  return 0;
}

总结分析过程

我们一开始提出用$dp[i][j]$表示从u数塔位置$(i,j)$到最底层，这就是它的意义所在，我们需要找到一个递推关系，也就是动态转移方程。所以我们在使用动态规划算法设计程序时，首先要明确$dp[i][j]$这个状态的意义。当然，这肯定是一个艰难的过程。
在我们明白这个$dp[i][j]$所表示的意义时，就要通过正推或者逆推得到状态转移方程。步骤1、2我这里分开是便于叙述，在思考时是万万不能分开的。要根据问题，怎样设计出合理的$dp[i][j]$表示的状态，得到状态转移方程。
最后，在前两步完成的情况下，思考出递推边界情况，可以通过正推状态转移方程也可以逆推状态转移方程得出边界。

上面的数塔问题包含最优子结构性质，下面再解析重叠子问题。

经典问题

求解斐波那契数列的第n项。

我们很容易写出递归式:

int f(int n)
{
    if(n < 0)
        return -1;
    if(n == 1 || n == 2)
        return 1;
    return f(n-1) + f(n-2);
}

对于该递归我们可以得到一棵二叉树:

图中，我们在对$f(5)$递归求解时调用了两次$f(3)$，我们明明可以只用求解一次然后将答案记录下来，再用时直接访问答案就可以了。这就是重叠子问题。这里就要提一下备忘录方法了，这其实是动态规划的变形，并且它将计算过的子问题都会保存到数组中，下一次遇见相同的子问题直接调用即可。

我们用$dp[n]$表示第$n$项斐波那契数列，不难得到其动态转移方程为
```
dp[n]=dp[n-1]+dp[n-2]
```
其递归边界dp[1]=1,dp[2]=1，所以我们可以写出使用自顶向下的备忘录方法求解斐波那契数列
```
array < int, 100> dp = {0};
int f(int n)
{
  if(n < 0)
      return -1;
  if(dp[n])
      return dp[n];
  if(n == 1 || n == 2)
      return dp[1] = dp[2] = 1;
  return dp[n] = f(n - 1) + f(n - 2);
}
```
当然我们也可以写成动态规划形式，假设求第$n$项斐波那契数列:
```
array < int, 47> dp = {0};        // 整形范围内，第47项斐波那契数列溢出
dp[1]=dp[2]=1;
for(int i=3;i<=n;i++)
{
  dp[i]=dp[i-1]+dp[i-2];
}
```
可以观察到在求解$dp[n]$的过程中，只有$dp[n-1]$和$dp[n-2]$有效，比如$dp[3]=dp[2]+dp[1]，dp[4]=dp[3]+dp[2]$，而$dp[1]$已经没有用处了。所以我们完全可以不用数组，只用两个变量$a,b$：
```
int f(int n)
{
  if(n < 0)
      return -1;
  if(n == 1 || n == 2)
      return 1;
  int a = 1, b = 1, ans = 0;
  for(int i = 3; i <= n; i++)
  {
      ans = a + b;
      a = b;
      b = ans;
  }
  return ans;
}
```
空间复杂度由$O(n)$下降到$O(1)$，不得不说这是一个巨大的飞跃。所以根据动态规划的递推式，我们可以通过观察来一定程度优化空间复杂度，这都是后话了。

综述

　　关于动态规划算法，我这里展示的只是冰山一角。每个人都会有其独特的理解，有人认为它是在填矩阵，有人认为它是一种拓扑排序（想来的确如此），如《哈姆雷特》一般。
对于我们普通人来说，不可能一次就完完全全的领悟。需要一段时间的沉淀，需要不断地总结、练习，以更上一层楼。
推荐阅读：
https://mp.weixin.qq.com/s/3h9iqU4rdH3EIy5m6AzXsg

月之燃梦

完全属于自己的安静的一隅

浅谈动态规划算法

LV1-初识

最优子结构

总结分析过程

上面的数塔问题包含最优子结构性质，下面再解析重叠子问题。

综述