动态规划法（九）想要更多例子？

本文将会介绍三个用动态规划法解决的例子，分别是：

• 楼梯台阶问题
• 二项式系数求解
• 最大乘积子数组问题

楼梯台阶问题

一个n阶的楼梯，一个婴儿每次爬一阶或两阶，试问一共有多少种办法爬完楼梯。

设f(n)为该问题的解，考虑最后一次的爬法，若最后一次爬一阶，则前面n-1阶楼梯有f(n-1)种办法，若最后一次爬两阶，则前面n-2阶楼梯有f(n-2)种办法，因此：

f(1)=1,f(2)=2,f(3)=3，….该数列为斐波那契数列，可以参考博客 动态规划法（一）从斐波那契数列谈起用动态规划法进行求解。

一个n阶的楼梯，一个婴儿每次爬一阶或两阶或三阶台阶，试问一共有多少种办法爬完楼梯。

同上面的解法一样，有：

其中，f(1)=1,f(2)=2,f(3)=4. 可以参考博客 动态规划法（二）找零钱问题用动态规划法进行求解。

二项式系数求解

对于二项式系数，有如下等式：

再结合 C0n=1,C1n=nCn0=1,Cn1=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）， 欢迎大家关注哦~~