本文将会介绍三个用动态规划法解决的例子，分别是：
- 楼梯台阶问题
- 二项式系数求解
- 最大乘积子数组问题
楼梯台阶问题
一个n阶的楼梯，一个婴儿每次爬一阶或两阶，试问一共有多少种办法爬完楼梯。
设f(n)为该问题的解，考虑最后一次的爬法，若最后一次爬一阶，则前面n-1阶楼梯有f(n-1)种办法，若最后一次爬两阶，则前面n-2阶楼梯有f(n-2)种办法，因此：
$$f(n)=f(n-1)+f(n-2).$$
f(1)=1,f(2)=2,f(3)=3，....该数列为斐波那契数列，可以参考博客动态规划法（一）从斐波那契数列谈起用动态规划法进行求解。
一个n阶的楼梯，一个婴儿每次爬一阶或两阶或三阶台阶，试问一共有多少种办法爬完楼梯。
同上面的解法一样，有：
$$f(n)=f(n-1)+f(n-2)+f(n-3).$$
其中，f(1)=1,f(2)=2,f(3)=4. 可以参考博客动态规划法（二）找零钱问题用动态规划法进行求解。
二项式系数求解
对于二项式系数，有如下等式：
$$C_{n}{k}=C_{n-1}{k}+C_{n-1}^{k-1}.$$
再结合$C_{n}{0}=1,C_{n}{1}=n$对该问题用动态规划法进行求解，本质上这也是一个递归关系式。Python代码如下：
import numpy as np
def binomial(n, k):
if k == 0:
return 1
elif k == 1:
return n
else:
table = np.array([[0] * (k + 1)] * n, dtype='int64')
for i in range(n):
table[i, 0] = 1
table[i, 1] = i + 1
for i in range(n):
for j in range(2, k+1):
if i+1 < j:
table[i, j] = 0
else:
table[i, j] = table[i-1, j] + table[i-1, j-1]
return table[n-1, k]
t = binomial(50, 10)
print(t)
最大乘积子数组问题
所谓的最大乘积子数组问题，指的是：给定一个数组A，寻找A的乘积最大的非空连续子数组。比如，数组 A = [-2, -3, 4]， 最大乘积子数组应为A,其和为24。
在博客动态规划法（八）最大子数组问题（maximum subarray problem）中，我们已经用动态规划法解决了最大子数组问题。对于最大乘积子数组问题，我们也可以类似地用动态规划法解决。但是，对于A中元素均为正数的情形，可以有更简单的方法。
首先对A中元素去对数，则原问题等价于最大子数组问题，找出最大和后，再用指数作用，就能得到A中元素均为正数的最大乘积子数组问题的解。其Python代码如下：
from math import log2, pow
# using dynamic programming to slove maximum subarray problem
def DP_maximum_subarray(old_arr):
# 对原数组取底为2的对数
arr = [log2(x) for x in old_arr]
# 对新数组求解最大子数组问题
# 并求出该子数组的开始坐标(begin_index)和结束坐标(end_index)
t = len(arr)
MS = [0]*t # 初始化MS数组
MS[0] = arr[0] # 动态规划法的初始值
# 动态规划法的子结构
for i in range(1, t):
MS[i] = max(MS[i-1]+arr[i], arr[i])
# 求解该子数组的开始坐标(begin_index)和结束坐标(end_index)
end_index = MS.index(max(MS))
begin_index = end_index
sum = arr[end_index]
while abs(sum- max(MS)) > pow(10, -5):
begin_index -= 1
sum += arr[begin_index]
return begin_index, end_index, pow(2, max(MS))
a = [1/2, 4, 1/2, 16, 1/8, 32, 2, 1/16]
begin_index, end_index, max_product = DP_maximum_subarray(a)
print([begin_index, end_index, max_product])
输出结果为：
[1, 6, 256.0]
最大乘积子数组问题的最大乘积为256，子数组开始坐标为1，结束坐标为6，因此子数组为[4, 1/2, 16, 1/8, 32, 2]。
注意：本人现已开通两个微信公众号： 用Python做数学（微信号为：python_math）以及轻松学会Python爬虫（微信号为：easy_web_scrape）， 欢迎大家关注哦~~
