动态规划

官方解释：
动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

动态规划是程序进阶路上必须要经过的一个山坡，所以记录在学习动态规划过程中的方法和思路。

动态规划系列文章一共分为九个部分，每一个部分都是一个独立的例子，难易程度逐渐递增。这九个例子分别是：

动态规划系列之一爬楼梯问题
动态规划系列之二最大和子数组
动态规划系列之三乘积最大子数组
动态规划系列之四梅花桩问题
动态规划系列之五打家劫舍
动态规划系列之六01背包问题
动态规划系列之七完全背包问题
动态规划系列之八多重背包问题
动态规划系列之九找零钱

爬楼梯问题

不管问题有多难，我们首先来个望闻问切。以下面这个爬楼梯问题作为开胃菜。请听题：

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。比如，每次走1级台阶，一共走10步，这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。

那么先不看答案，你觉得这一个问题该如何解决呢？从下往上一步一步的走，for循环尝试所有的办法吗？每一步的走法都会影响后面的走法，所以计算的量非常庞大。那么使用动态规划的解题思路如何处理呢？

动态规划问题的解决方式有几个固定的套路，个人总结为：

建立数学模型
状态转移方程
确立边界值

第一步建立数学模型

假设走到第10级台阶有f(10)种方法，走到第9级台阶有f(9)种方法。记住这里f(10)就是走10级台阶走法的数量，这是动态规划的常见数学模型

第二步状态转移方程

走到 10 级台阶时前面有两种可能，一种是从第8级台阶走上来，一次跨了2级台阶；或者从第9级台阶走上来，一次跨了1级台阶。所以说走第10级台阶的总数 = 到第9级台阶的走法 + 到第8级台阶的走法

f(10) = f(9) + f(8)

同样道理，走到第9级台阶时肯定有两个可能，要么从第7级台阶过来，要么从第8级台阶过来。所有

f(9) = f(8) + f(7)
f(8) = f(7) + f(6)
f(7) = f(6) + f(5)
.....

总结状态转移方程就是：

f(n) = f(n-1) + f(n-2)

第三步确立边界值

第1级台阶只有一种走法，就是1步跨上去，第2级台阶有两种走法，分别是每次跨一步，两次；一次跨两级台阶，一次;所以：

f(1) = 1
f(2) = 2

代码实现

有了以上的理论基础就可以写出代码来实现这个上楼梯问题。

def up(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    total = up(n-1)  + up(n-2)

    return total

result = up(10)
print('台阶的走法为：%d' % result)

台阶的走法为：89

换一个思路

以上的思路是一种由上向下的解法思路，从最后一个值不断向前推导，直到遇到边界情况。可以换一个思路，从下往上看。走第一步台阶只有1种方法，走第二部台阶有2种方法，第三步台阶可以从第1步跨2级上来，也可以是从第2步跨1级上来。所以：
已知：边界情况 f(1) = 1, f(2) = 2 ,并且知道f(3) = f(1) + f(2)
求解：f(10)

def up(n):
    if n == 1:
        return 1

    if n == 2:
        return 2
    
    a = 1
    b = 2
    sum_num = 0
    for i in range(3,n+1):
        # 状态转移方程：f(n) = f(n-1) + f(n-2)
        sum_num = a + b
        a = b
        b = sum_num

    return sum_num

总结

那么到这里就已经完成了走楼梯的解法，从代码量来看，核心代码不超过10行，是不是没有想象的那么难呢？是的，动态规划并不是想象的那么难，只要能领会思路，了解解题套路就畅通无阻啦。
另外可以看到动态规划问题既可以使用迭代解法，也可以使用循环解法。从常见的解题思路来看，循环的方法比较多。那么如果你已经理解了动态规划的建立数学模型 + 状态转移 + 确立边界值，说明本篇就完全掌握了。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/194256.html