前面提到了动态规划的原理以及一个计算最短延迟时间的例子，联想到之前说过的隐马尔科夫模型（HMM）中的forward-backward算法、时序分类模型CTC中的动态规划算法，这些无非是在降低问题的计算时间复杂度。如果不使用DP算法来解决的话，原问题当然也是可以解决的，只不过计算量会非常大。
那么到底什么是DP算法呢？细想一下，DP算法的精髓无非就是把一个复杂的问题拆分成一些子问题，然后“递归”计算每个子问题的解，并且“记住”了每一个计算结果，这个技巧一般称为“Memoization”。在一般的递归计算中，会有许多子问题被重复计算，而DP算法则避免了重复计算的消耗。换句话说，DP算法对历史作了记录表，后来的子问题只用查询记录表即可获取值。
不妨看看下面两个程序之间的差异，它们都是为了解决同一个问题：
算法一：
int binom(int a, int b)
{
if (b==0 || b==a) return 1;
else return binom(a-1,b-1)+binom(a-1,b);
}
算法二：
int binomDP(int a, int b)
{
int binom[a+1][a+1];
for (int i=0; i<=a; i++)
{
for (int j=0; j<=i; j++)
{
if (j==0 || j==i) binom[j] = 1;
else binom[j] = binom[i-1][j-1] + binom[i-1][j];
}
}
return binom[a];
}
那么，很显然算法二使用了DP算法来解决，而算法一仅仅是常规的递归计算，这中间当然会有同一个值被计算了多次，而算法二中每次计算都会保存在数组中，不会有重复的计算。
下面再看一个简单的DP问题，题目是这样的：现在假如有一个梯子一共有20格，你可以每次跨一步，也可以每次跨两步，还可以每次跨三步，为了从梯子底部到达梯子顶部，请问一共有多少种不同的走法？
如果按照传统的迭代方法的话，这个问题的计算复杂度应该是指数级的，但是我们可以使用DP算法将问题的复杂度降级为O(n)，下面我用C++语言来解决上面所说的梯子问题。
#include <iostream>
using namespace std;
int main()
{
int i;
int ladders=20;
long num[ladders];
for(i=0;i<ladders;i++)
{
num=0;
}
num[0]=1;
for(i=0;i<ladders;i++)
{
if(i+1<ladders)
num[i+1]+=num;
if(i+2<ladders)
num[i+2]+=num;
if(i+3<ladders)
num[i+3]+=num;
}
cout << num[ladders-1] << endl;
return 0;
}
计算结果是:一共可以有66012种方法。
来源：张泽旺 深度学习每日摘要
智造家