动态规划法(九)想要更多例子?

  1. 云栖社区>
  2. 博客>
  3. 正文

动态规划法(九)想要更多例子?

jclian91 2018-06-06 21:58:53 浏览677
展开阅读全文

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

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

楼梯台阶问题

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

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

f(n)=f(n1)+f(n2).f(n)=f(n−1)+f(n−2).

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

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

同上面的解法一样,有:

f(n)=f(n1)+f(n2)+f(n3).f(n)=f(n−1)+f(n−2)+f(n−3).

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

二项式系数求解

  对于二项式系数,有如下等式:

Ckn=Ckn1+Ck1n1.Cnk=Cn−1k+Cn−1k−1.

再结合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), 欢迎大家关注哦~~

网友评论

登录后评论
0/500
评论
jclian91
+ 关注