动态规划

动态规划（Dynamic Programming）

动态规划在数学上属于运筹学的分支，是求解决策过程最优化的数学方法，同时也是计算机科学与技术领域中一种常见的算法思想。

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题，按顺序求解子问题。前一子问题的解，为后一子问题的求解提供了有用的信息。

在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其它局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

动态规划的本质是对问题状态的定义和状态转移方程的定义。动态规划通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。因此在一个典型的动态规划问题上，需要定义问题状态以及写出状态转移方程，这样对于问题的解答就会一目了然。

爬楼梯

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶，要求求出一共有多少种走法。

比如，每次走1级台阶，一共走10步，这是其中一种走法，可以简写成[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]。再比如，每次走2级台阶，一共走5步，这是另一种走法，可以简写成[2, 2, 2, 2, 2]。当然，除此之外，还有很多很多种走法。

暴力枚举的算法利用排列组合的思想，通过多重循环遍历出所有的可能性。但是暴力枚举的时间复杂度是指数级的，有没有更高效的解法呢？

要不找个楼梯走一下试试吧！正好能减肥！

动态规划是一种分阶段求解决策问题的数学思想，它不止用于编程领域，也应用于管理学、经济学、生物学等。总的来说就是大事化小，小事化了。

在爬楼梯问题中，假设你只差最后一步就走到第10级台阶，这时候会出现几种情况？

当然是两种喽，因为每一步只许走1级或2级，所以最后一步要么是从第9级走到第10级，要么是从第8级走到第10级。

接下来就引申出了一个新的问题，如果已知从第0级走到第9级的走法有X种，从第0级走到第8级的走法有Y种，那么从第0级走到第10级的走法就有X + Y种。

为了方便表达，我们把10级台阶的走法数量简写为F(10)，此时F(10) = F(9) + F(8)。那么如何计算F(9)和F(8)呢？

利用刚才的思路可以很容易地推断出F(9) = F(8) + F(7)， F(8) = F(7) + F(6)。这样我们就把一个复杂的问题分阶段进行简化，逐步简化成简单的问题，这就是动态规划的思想。

当只有1级台阶和2级台阶的时候，显然分别只有1种和2种走法。由此可以归纳出递推公式：

动态规划当中包含了三个重要的概念：

• 最优子结构

• 边界

• 状态转移方程

刚才分析得出的F(10) = F(9) + F(8)中，F(9)和F(8)就是F(10)的两个子问题。爬楼梯是计数问题，这里按最后一步划分互不重叠的走法，再相加，而不是在多个解中选择最优解。

当只有1级台阶或2级台阶时，我们可以直接得出结果，无需继续简化。因此F(1)和F(2)就是问题的边界。如果一个问题没有边界，将永远无法得到有限的结果。

F(n) = F(n-1) + F(n-2)是阶段与阶段之间的状态转移方程，这是动态规划的核心，决定了问题的每一个阶段与下一阶段的关系。

既然已经归纳出了F(n) = F(n-1) + F(n-2)，又知道了边界，那就可以直接用递归的思路实现。

爬楼梯（递归）

#include <stdio.h>

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

递归的确可以计算出最终答案，可是其时间复杂度却是指数级的。

二叉树的结点个数就是递归方法所需要计算的次数，因此递归方法的时间复杂度为$O(2^n)$。

可以发现在递归树中，有些相同的参数被重复计算了，越往下走，重复的越多。

可是一定要对F(n)自顶向下做递归运算吗？采用自底向上，用迭代的方法也可以推导出结果。

之前已经得出结论，F(1) = 1，F(2) = 2：

因为F(3) = F(1) + F(2)，经过一次迭代可以计算出F(3)：

第二次迭代，由于F(4)只依赖于F(2)和F(3)，而F(3)已经在上一次迭代计算得出，无需重复计算：

爬楼梯（动态规划）

#include <stdio.h>

int climb_dp(int n) {
    if (n <= 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }

    int num1 = 1;
    int num2 = 2;
    int sum;
    for (int i = 3; i <= n; i++) {
        sum = num1 + num2;
        num1 = num2;
        num2 = sum;
    }
    return sum;
}

代码约定n为非负整数；n≤0返回0。示例范围内计数不溢出。