动态规划入门

五大常用算法： 动态规划

引入

1. 基本概念

动态规划英文 Dynamic Programming，是求解决策过程最优化的数学方法，后来沿用到了编程领域。

动态规划的大致思路是把一个复杂的问题转化成一个分阶段逐步递推的过程，从简单的初始状态一步一步递推，最终得到复杂问题的最优解。

动态规划解决问题的过程分为两步：

• 寻找状态转移方程
• 利用状态转移方程式自底向上求解问题

找出来以下三点，题目就完成了80%：

• 状态表示：如何用数组表示实际问题
• 状态转移：如何由已知状态表示未知状态
• 状态边界：哪些状态不用转移就可以得到

具有以下三个特性的问题适用于动态规划：

• 最优子结构：全局最优解包含局部最优解
• 重叠子问题：子问题出现大量重叠
• 无后效性：每次决策不影响之后的决策

2. 爬楼梯问题

题目描述：

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

简化题目：

假设这里只有十级台阶，方便于表述。

动态规划思路：

动态规划简单来说就是：大事化小，小事化了。

那这道题目来讲，假设还差最后一步走到第十级台阶，这时候有两种情况：还有 1 级台阶/ 2级台阶。 如果暂时不考虑 08 级的过程，也不管 09 级的过程，那么 0~10级的走法就是这两个方法的数值之和。

这时我们不考虑总共的台阶为 10，换为 8/9，我们重新考虑分别走到第八级和第九级的方法。这里我们先假设走到第 N 级台阶的方法为 F(N)： F(10)=F(8)+F(9)

同理：

F(9)=F(8)+F(7)

F(8)=F(7)+F(6)

此时： F(N)=F(N-1)+F(N-2) 是阶段与阶段之间的 状态转移方程

递归实现

int getNumWays(int n)        \\二叉树
{
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    else {
        return getNumWays(n - 1) + getNumWays(n - 2);
    }
}

备忘录算法

上面的算法时间复杂度很高，树的结点个数是递归的计算次数。树的高度为 N-1，节点个数接近 2^n-1,时间复杂度为 O(2^n)。

如果用树状图来表示的话，我们可以得到一颗二叉树：

二叉树演示

可以看到，重复计算了很多相同的参数输入。我们可以通过数组或者哈希表记录节点值来完成时间复杂度的简化。 这里我们用c++中STL来实现：

map <int, int> cache;
int getNumWays(int n)
{
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    if (cache.count(n)) {
        return cache[n];
    }
    else {
        int value = getNumWays(n - 1) + getNumWays(n - 2);
        cache[n] = value;
        return value;
    }
}

在以上代码中，集合 cache 是一个备忘录。当每次需要计算F(N)的时候，会首先从 cache 中寻找匹配元素。如果存在，就直接返回结果，如果不存在，就计算出结果，存入备忘录中。 可以简单得到，这个算法复杂度为 O(N)。

动态规划

虽然到上面一步已经实现了时间复杂度的优化，但还算不上真正的动态规划。 前面提到：

动态规划解决问题的过程分为两步：

• 寻找状态转移方程
• 利用状态转移方程式自底向上求解问题

我们继续尝试自下而上迭代计算结果，由于每一次步的结果只依赖于之前的两个状态，所以我们只用推导新的状态。

int getNumWays(int n)
{
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    int a = 1, b = 2, temp = 0;

    for (int i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }

    return temp;
}

程序从 i=3 开始迭代，一直到 i=n 结束。每一次迭代，都会计算出多一级台阶的走法数量。迭代过程中只需保留两个临时变量a和b，分别代表了上一次和上上次迭代的结果。 为了便于理解，我引入了temp变量。temp代表了当前迭代的结果值。

基本思想

基本思想是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

总结

在利用动态规划求解问题的过程中，比较难的是找到状态转移方程，当前项和前两项的关系。 当然例题也只是最简单的动态规划，是一道板子题。

找到这种关系后，需要转化思路，自底向上编写程序，这样才能降低时间复杂度。

>动态规划剖析