??本文將會介紹三個(gè)用動態(tài)規(guī)劃法解決的例子，分別是：

• 樓梯臺階問題
• 二項(xiàng)式系數(shù)求解
• 最大乘積子數(shù)組問題

樓梯臺階問題

一個(gè)n階的樓梯，一個(gè)嬰兒每次爬一階或兩階，試問一共有多少種辦法爬完樓梯。

設(shè)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，....該數(shù)列為斐波那契數(shù)列，可以參考博客動態(tài)規(guī)劃法（一）從斐波那契數(shù)列談起用動態(tài)規(guī)劃法進(jìn)行求解。

一個(gè)n階的樓梯，一個(gè)嬰兒每次爬一階或兩階或三階臺階，試問一共有多少種辦法爬完樓梯。

同上面的解法一樣，有：
$$f(n)=f(n-1)+f(n-2)+f(n-3).$$
其中，f(1)=1,f(2)=2,f(3)=4. 可以參考博客動態(tài)規(guī)劃法（二）找零錢問題用動態(tài)規(guī)劃法進(jìn)行求解。

二項(xiàng)式系數(shù)求解

??對于二項(xiàng)式系數(shù)，有如下等式：
$$C_{n}^{k}=C_{n-1}^{k}+C_{n-1}^{k-1}.$$
再結(jié)合$C_{n}^{0}=1,C_{n}^{1}=n$對該問題用動態(tài)規(guī)劃法進(jìn)行求解，本質(zhì)上這也是一個(gè)遞歸關(guān)系式。Python代碼如下：

import numpy as npdef binomial(n, k):if k == 0:return 1elif k == 1:return nelse:table = np.array([[0] * (k + 1)] * n, dtype='int64')for i in range(n):table[i, 0] = 1table[i, 1] = i + 1for i in range(n):for j in range(2, k+1):if i+1 < j:table[i, j] = 0else:table[i, j] = table[i-1, j] + table[i-1, j-1]return table[n-1, k]t = binomial(50, 10) print(t)

最大乘積子數(shù)組問題

??所謂的最大乘積子數(shù)組問題，指的是：給定一個(gè)數(shù)組A，尋找A的乘積最大的非空連續(xù)子數(shù)組。比如，數(shù)組 A = [-2, -3, 4]， 最大乘積子數(shù)組應(yīng)為A,其和為24。
??在博客動態(tài)規(guī)劃法（八）最大子數(shù)組問題（maximum subarray problem）中，我們已經(jīng)用動態(tài)規(guī)劃法解決了最大子數(shù)組問題。對于最大乘積子數(shù)組問題，我們也可以類似地用動態(tài)規(guī)劃法解決。但是，對于A中元素均為正數(shù)的情形，可以有更簡單的方法。
??首先對A中元素去對數(shù)，則原問題等價(jià)于最大子數(shù)組問題，找出最大和后，再用指數(shù)作用，就能得到A中元素均為正數(shù)的最大乘積子數(shù)組問題的解。其Python代碼如下：

from math import log2, pow# using dynamic programming to slove maximum subarray problem def DP_maximum_subarray(old_arr):# 對原數(shù)組取底為2的對數(shù)arr = [log2(x) for x in old_arr]# 對新數(shù)組求解最大子數(shù)組問題# 并求出該子數(shù)組的開始坐標(biāo)(begin_index)和結(jié)束坐標(biāo)(end_index)t = len(arr)MS = [0]*t # 初始化MS數(shù)組MS[0] = arr[0] # 動態(tài)規(guī)劃法的初始值# 動態(tài)規(guī)劃法的子結(jié)構(gòu)for i in range(1, t):MS[i] = max(MS[i-1]+arr[i], arr[i])# 求解該子數(shù)組的開始坐標(biāo)(begin_index)和結(jié)束坐標(biāo)(end_index)end_index = MS.index(max(MS))begin_index = end_indexsum = arr[end_index]while abs(sum- max(MS)) > pow(10, -5):begin_index -= 1sum += 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])

輸出結(jié)果為：

[1, 6, 256.0]

最大乘積子數(shù)組問題的最大乘積為256，子數(shù)組開始坐標(biāo)為1，結(jié)束坐標(biāo)為6，因此子數(shù)組為[4, 1/2, 16, 1/8, 32, 2]。

注意：本人現(xiàn)已開通兩個(gè)微信公眾號： 用Python做數(shù)學(xué)（微信號為：python_math）以及輕松學(xué)會Python爬蟲（微信號為：easy_web_scrape）， 歡迎大家關(guān)注哦~~

總結(jié)

以上是生活随笔為你收集整理的动态规划法（九）想要更多例子？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。