動態(tài)規(guī)劃Dynamic programming, since 2020-04-26

DP是用途廣泛的問題解決思路/思想，而不是特定的算法歪泳。主要用于優(yōu)化問題(optimisation)萝勤，求解最優(yōu)方法。如果待解決的問題有如下特性呐伞，則適用于DP敌卓。
適用范圍

Simple Subproblems簡單子問題: There has to be some way of repeatedly breaking the global optimisation problem into subproblems. Moreover, there should be a way to parameterise subproblems with just a few indices, like i, j, k, and so on.
Subproblem optimisation子問題優(yōu)化: An optimal solution to the global problem must be a composition of optimal subproblem solutions.
Subproblem overlap子問題混疊: Optimal solutions to unrelated subproblems can contain subproblems in common.

(2020.09.13 Sun輸入，2020.09.04筆記)

解決的問題類型

求最大/小值
方案是否可行
方案的總數(shù)
注意: 求所有方案和結(jié)果的具體內(nèi)容伶氢，可能無法使用DP趟径。

問題特征

遞歸+重復(fù)，具體來說符合[一個(gè)模型三個(gè)特征]癣防。

模型
多階段決策最優(yōu)解模型
特征
- 最優(yōu)子結(jié)構(gòu)蜗巧，即每個(gè)階段都有最優(yōu)解
- 無后效性，當(dāng)前階段最優(yōu)解僅與上個(gè)階段最優(yōu)解有關(guān)蕾盯，不在乎上個(gè)階段最優(yōu)解如何得出
- 重復(fù)子問題幕屹，自下而上的方式有重復(fù)子問題。比如级遭，一個(gè)8 * 8的格子望拖，每次向右/下走一步，有多少種走法挫鸽？相當(dāng)于第一次從頂點(diǎn)向右或下说敏，走到一個(gè)7 * 7的格子，and so on.設(shè)左上角的點(diǎn)是(0,0)右下角的點(diǎn)(7,7)丢郊，起點(diǎn)的位置是(x,y)盔沫，#path(x,y) = #path(x+1,y) + #path(x,y+1)
- 子問題間保持獨(dú)立，也可理解為無后效性

(2020.09.13 Sun輸入蚂夕，2020.09.04筆記)

典型問題

背包問題backpack
資源分配
區(qū)間模型
樹型模型

背包問題：類似的問題有青蛙跳井問題和取硬幣問題迅诬。以價(jià)值為狀態(tài)腋逆。背包的詳細(xì)分解見背包九講婿牍。只看簡單的背包問題0-1背包。有一個(gè)背包和n個(gè)物品惩歉，每個(gè)物品只有一個(gè)等脂，其重量(或價(jià)值)為 $W_i$ ，其體積 $V_i$ 撑蚌，包的總體積 $V$ 上遥，求如何取物品保證包裝的足夠滿，且總重量最大争涌。
d(i,j)表示把第i, i+1, i+2, ...n個(gè)物品放在容量為j的背包中的最大總重量粉楚，或者當(dāng)前在第i層，背包剩余容量為j時(shí)接下來的最大重量和，有 $d(i,j)= max(d(i+1,j),\space d(i+1,j-V_i)-W_i)$ 模软。邊界條件 $i>n$ 伟骨，則 $d(i,j)=0$ 。
資源分配：類似的有花店櫥窗布置和馬廄問題燃异。有m個(gè)資源携狭，分給n個(gè)部分，第i個(gè)部門獲得j資源時(shí)有盈利值v(i,j)回俐，如何分配使得盈利最大逛腿？最大是多少？
設(shè)f(i,j)表示前 $i$ 個(gè)部門分配 $j$ 個(gè)資源時(shí)獲得的最大盈利仅颇，可拆分為前 $i-1$ 個(gè)部門分配 $k$ 個(gè)資源和第 $i$ 個(gè)部門分配 $j-k$ 個(gè)資源单默，通過遍歷 $k$ 可以找到最大盈利。有 $f(i,j) = max(f(i-1,k) + v(i,j-k)), 0\leq k \leq j$ 忘瓦。
區(qū)間模型：參考LIS/LCS/回文串的cases雕凹。

Case 1 Matrix chain-product矩陣連乘積:
（2020.04.26）
這個(gè)問題里我們關(guān)注矩陣chain-product的計(jì)算量。
$A = A_{0} \cdot A_{1} \cdot A_{1} \cdots A_{n-1}$
其中 $A_{i}$ 是尺寸為 $d_{i}\times d_{i+1}$ 的矩陣政冻， $i = 0, 1, 2,...,n-1$ 枚抵。注意到矩陣乘法可以使用乘法結(jié)合律，即 $B \cdot (C \cdot D) = (B \cdot C) \cdot D$ 明场。
設(shè) $B$ 的尺寸為 $2\times10$ 汽摹， $C$ 的尺寸為 $10\times50$ ， $D$ 的尺寸為 $50\times20$ 苦锨。采用 $B \cdot (C \cdot D)$ 的方式計(jì)算逼泣，總計(jì)算次數(shù)為
$10\times50\times20(C\times D的次數(shù))+2\times10\times20(B\times C、D相乘結(jié)果的次數(shù))=10400$

采用 $(B\times C)\times D$ 的方式計(jì)算舟舒，總計(jì)算次數(shù)為
$2\times10\times50(B\times C計(jì)算的次數(shù))+2\times 50 \times 20(B拉庶、C相乘的結(jié)果與D相乘的次數(shù))=3000$

由此可見parenthesisation對于矩陣連乘積的運(yùn)算量影響顯著。The matrix chain-product problem is to determine the parenthesisation of the expression define the product $A$ that minimises the total number of scalar multiplications performed.

定義子問題
(2020.04.27 Mon)
首先確認(rèn)該問題可以分解為子問題秃励，即to compute the best parenthesisation for some subexpression $A_{i} \cdot A_{i+1} \cdots A_{j}$ 氏仗。定義 $N_{i,j}$ 為該表達(dá)式最少乘法次數(shù)。因此初始問題可以轉(zhuǎn)化為計(jì)算 $N_{0,n-1}$ 夺鲜。
解決子問題
一個(gè)觀察的結(jié)論: it is possible to characterise an optimal solution to a particular subproblem in term of optimal solutions to its subproblems. We call this property the subproblem optimality condition.
$A_{i} \cdot A_{i+1} \cdots A_{j}$ 的parenthesisation可表述為 $(A_{i} \cdots A_{k}) \cdot (A_{k+1} \cdots A_{j}), k \in {i,i+1,\cdots,j-1}$ 皆尔。問題轉(zhuǎn)化為計(jì)算 $N_{i,j}$ 在不同 $k$ 位置取得的最小值。
設(shè)計(jì)動態(tài)規(guī)劃算法
Optimal subproblem解決方案的 $N_{i,j}$ 有 $N_{i,j} = \min_{i\le k<j} (N_{i,k}+N_{k+1,j} +d_{i}d_{k+1}d_{j+1})$
其中 $N_{i,j}$ 表示 $A_{i}\times A_{i+1} \cdots \times A_{j}$ 的計(jì)算量/計(jì)算次數(shù)币励， $d_{i}$ : #rows of $A_{i}$ 慷蠕。
(2020.04.28 Tues)
即，在 $A_{i}\times A_{i+1} \times \cdots \times A_{k} \times A_{k+1} \times A_{k+2} \times \cdots A_{j}$ 中食呻，前一項(xiàng) $A_{i}\times A_{i+1}\times \cdots A_{k}$ 的運(yùn)算次數(shù)是 $N_{i,k}$ 流炕，后一項(xiàng) $A_{i}\times A_{k+1}\times \cdots A_{j}$ 的運(yùn)算次數(shù)是 $N_{k+1,j}$ 澎现。前一項(xiàng)的尺寸是 $d_{i}d_{k+1}$ ，后一項(xiàng)的尺寸是 $d_{k+1}d_{j+1}$ 每辟，因此前后兩項(xiàng)相乘的運(yùn)算次數(shù)是 $d_{i}d_{k+1}d_{j+1}$ 昔头。于是可以用bottom-up fashion來計(jì)算 $N_{i,j}$ ，從0開始生成一個(gè)表影兽，存儲 $N_{i,j}$ 的所有值揭斧。對任意非負(fù)整數(shù) $i$ ，有初始條件 $N_{i,i}=0$ 峻堰。由 $N_{i,j}$ 的公式和初始條件讹开，可求得 $N_{i,i+1}$ ，并由 $N_{i,i+1}$ 可推得 $N_{i,i+2}$ 捐名，進(jìn)而推得 $N_{0,i-1}$ 旦万。

def matrix_chain(d):
    # d: a list of n+1 numbers such that size of kth matrix is d[k]-by-d[k+1]
    n = len(d) - 1                          # number of matrices
    N = [[0] * n for i in range(n)]         # initialise n-by-n result to zero
    for b in range(1, n):                    # number of products in subchain
        for i in range(n-b):                # start of subchain
            j = i + b                       # end of subchain
            N[i][j] = min(N[i][k]+N[k+1][j]+d[i]*d[k+1]*d[j+1] for k in range(i,j))
    return N

Case 2 Text sequence alignment & LCS(longest common sequence) 文本處理和最長相同序列
(2020.04.28 Tues)
問題源自兩類實(shí)際問題，即比較序列的相似性(i.e., DNA/代碼)镶蹋。
Subsequence子序列: 從原序列中抽取成艘，并按原有順序排列的序列，未必contiguous連續(xù)抽取贺归。如 $CTAG$ 是 $\underline{C}GATAA\underline{T}TG\underline{AG}A$ 的子序列淆两。

Longest Common Subsequence (LCS)最長共同子序列
問題描述：給定兩個(gè)序列 $X=x_0x_1\cdots x_{n-1}$ 和 $Y=y_0y_1\cdots y_{m-1}$ ，找出同時(shí)為 $X$ 和 $Y$ 的子序列中最長的一個(gè)拂酣。
Brute-force approach: 列舉出 $X$ (長度為 $n$ )的所有子序列秋冰，共計(jì) $2^{n}$ 個(gè)，逐個(gè)判斷是否為 $Y$ (長度為 $m$ )的子序列婶熬，每次判斷的時(shí)間復(fù)雜度 $O(m)$ 剑勾，因此總的時(shí)間復(fù)雜度為 $O(2^{n}m)$ ，效率低下赵颅。而用動態(tài)規(guī)劃有如下解決方案虽另。
(2020.04.29 Wed)
DP方案用于優(yōu)化問題，即尋找"最好的"解決方案饺谬。如果問題有如下特性捂刺，則可以用DP方案解決:

simple subproblems: there has to be some way of repeatedly breaking the global optimisation problem into subproblems. Moreover, there should be a way to parameterise subproblems with just a few indices, like $i,j,k$ , and so on.
subproblem optimisation: an optimal solution to the global problem must be a composition of optimal subproblem solution.
subproblem overlap: optimal solutions to unrelated subproblems can contain subproblems in common.

思路: (提取子問題)用index尋址兩個(gè)字符串 $X$ 和 $Y$ 。定義 $X[0:j]$ 和 $Y[0:k]$ 的LCS的值為 $L_{j,k}$ 商蕴。比如 $L_{10,12}$ 表示 $X[0:10]$ 和 $Y[0:12]$ 的LCS的值叠萍，于是 $X$ 的indices可取 $0,1,2,\cdots 9$ 芝发， $Y$ 的indices可取 $0,1,2,\cdots 11$ 绪商。這種定義方式可根據(jù)子問題重寫 $L_{j,k}$ 。針對 $L_{10,12}$ 考慮下面兩種情況:

兩個(gè)子序列的最后一位相同辅鲸，i.e., $X[9]=Y[11]$ 格郁，則有 $L_{10,12}=1+L_{9,11}$ ，推廣
$L_{j,k}=1+L_{j-1,k-1} \quad if \ x_{j-1}=y_{k-1}.$
兩個(gè)子序列的最后一位不同，此時(shí)兩個(gè)序列的common subsequence不能同時(shí)包含 $X[9]$ 和 $Y[11]$ ，也就是其common subsequence或者以 $X[9]$ 結(jié)尾或者以 $Y[11]$ 結(jié)尾，或者不以其中任一個(gè)結(jié)尾构挤，但一定不會是both物蝙。因此得到 $L_{9,11}=max(L_{9,10},L_{8,11})$ ，推廣 $L_{j,k}=max(L_{j-1,k},L_{j,k-1}) \quad if \ x_{j-1}\ne y_{k-1}.$

初始條件: $X[0:0]$ 為空字符萝究，因此 $L_{0,k}=0 \ for j=0,1,\cdots, n$ ，同樣的 $Y[0:0]$ 為空， $L_{j,0} = 0 \ for j = 0,1,2,\cdots,m$ 拇厢。
$L_{j,k}$ 的定義滿足子問題優(yōu)化，也使用了子問題重疊晒喷。用 $L_{j,k}$ 設(shè)計(jì)DP算法非常直接孝偎，設(shè) $0 \le j \le n, 0 \le k \le m$ ，創(chuàng)建一個(gè) $(n+1)\times (m+1)$ 的array $L$ 凉敲。所有元素的初始值為0衣盾，特別是 $L_{j,0},L_{0,k}$ 的值都為0。通過iteration求array $L$ 中的值爷抓，直到求出 $L_{n,m}$ 势决。

def lcs(X, Y):
    # return L, in which L[j][k] is length of LCS for X[0:j] and Y[0:k]
    n, m = len(X), len(Y)
    L = [ [0] * (m+1) for k in range(n+1)]
    for j in range(n):
        for k in range(m):
            if X[j] == Y[k]:
                L[j+1][k+1] = L[j][k] + 1 # align this match
            else:
                L[j+1][k+1] = max(L[j][k+1],L[j+1][k]) # choose to ignore one character
    return L

復(fù)雜度: $O(nm)$ .
lcs函數(shù)求出了LCS的長度，但不是LCS的序列蓝撇，下面這個(gè)函數(shù)可以求得LCS序列徽龟。

def lcs_solution(X, Y, L):
    solution = []
    j, k = len(X), len(Y)
    while L[j][k] > 0:
        if X[j-1] == Y[k-1]:
            j -= 1
            k -= 1
        elif L[j-1][k] >= L[j][k-1]:
            j -= 1
        else:
            k -= 1
    return ''.join(reversed(solution))

復(fù)雜度: $O(n+m)$ .

(2020.09.13 Sun輸入，2020.09.10筆記)
Case 3 Longest Increasing Sequence LIS 最長上升序列
求一個(gè)序列中的最長上升序列有多長唉地。序列s中任一個(gè)index對應(yīng)的最長上升序列長度是f(i)据悔，有 $f(i) = max(f(j))+1, i>j \space and \space s[i]>s[j]$
復(fù)雜度 $O(n^2)$

Case 4 回文串(palindrome)兩個(gè)問題

一個(gè)字符串中palindrome的最長長度，2) 如果不是回文串耘沼，最少加多少可以成為一個(gè)palindrome极颓。
字符串表示為s，其中元素為s[0],...,s[n]群嗤。對于序列s[i,...,j]菠隆，其中最長回文串長度為f[i][i]，有 $f[i][j] = max(f[i+1][j], f[i][j-1], f[i+1][j-1]+2|s[i]=s[j])$
初始條件狂秘， $f[i][i]=1$ 骇径。當(dāng) $s[i]=s[i+1]$ ，有 $f[i][i+1]=2$ 者春，當(dāng) $s[i]!=s[j]$ 破衔，有 $f[i][i+1] = 1$ 。
最少加入多少個(gè)字符可以成為palindrome钱烟。序列s中的s[i,...j] (i<j)部分需要加入最少d[i][j]個(gè)字符串能夠成為palindrome晰筛，當(dāng) $s[i]=s[j]$ 嫡丙，有 $d[i][j]=d[i+1][j-1]$ 。當(dāng) $s[i]!=s[j]$ 读第，有 $d[i][j] = min(d[i+1][j],d[i][j-1])+1$

(2022.09.04 Sun)
Case 4.1 leetcode 53 連續(xù)子數(shù)組最大和
給定一個(gè)整數(shù)數(shù)組 nums 曙博，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和怜瞒。

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大父泳，為 6。

建模：如果dp[i]表示以第i個(gè)結(jié)尾的最大序列和吴汪，而這個(gè)dp的狀態(tài)方程為
$dp[0] = a[0]$ $dp[i] = max(dp[i-1]+a[i], a[i])$
如果以前一個(gè)為截至的最大子序列和大于0尘吗，那么就在序列中加入當(dāng)前元素，否則當(dāng)前元素拋棄之前的序列以自己為首元素重新計(jì)算序列浇坐。

longest subsequence with max sum

代碼如下

def max_subsequence(nums):
    dp = [0] * (len(nums))
    Max, dp[0] = nums[0], nums[0]
    for i, e in enumerate(nums[1:]):
        dp[i+1] = max(dp[i]+e, e)
        if dp[i+1] > Max:
            Max = dp[i+1]
    return Max

** Case 4.2 leetcode 152 連續(xù)子數(shù)組最大乘積**
整數(shù)數(shù)組 nums 睬捶，請你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個(gè)數(shù)字），并返回該子數(shù)組所對應(yīng)的乘積近刘。

輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6擒贸。

(2022.09.23 Fri)
與前面的最大和問題不同，最大乘積會引入負(fù)值觉渴，一個(gè)最大值乘以負(fù)值介劫，瞬間成為最小值。為了避免負(fù)值帶來的誤差案淋，這里引入兩個(gè)dp數(shù)組座韵，分別保存最大值和最小值，只需要保證絕對值最大踢京，就可以求出所要的答案誉碴，公式為
$dpmax[i] = max(dpmax[i-1] * nums[i], dpmin[i-1] * nums[i], nums[i])$
$dpmin[i] = min(dpmax[i-1] * nums[i], dpmin[i-1] * nums[i], nums[i])$

dynamic programming max product.png

(2020.09.03 Thur)
Case 5 (rt對沖面試) 一個(gè)數(shù)組(長度n)代表了是一個(gè)股價(jià)的時(shí)間序列，可按照這個(gè)序列中的價(jià)格買入或賣出瓣距。如果最多可以進(jìn)行兩次買入賣出操作黔帕，計(jì)算在該時(shí)間序列中可獲得的最大收益。
思路：第一步計(jì)算index從0到i的序列中從0到每個(gè)index做一次買入賣出操作可獲得的最大收益mp1蹈丸。第二步成黄，計(jì)算從i+1到結(jié)尾(n-1)的序列中從i+1開始到每個(gè)index做一次買入賣出操作可獲得的最大收益mp2。第三步逻杖，i遍歷從0到n-1奋岁，計(jì)算 $max(mp1+mp2)$ 。

def get_max_profit(ar,profit_table,starting,ending):
    if ending <= starting:
        return 'Error'
    tmp = ar[ending]
    for e in ar[starting:ending]:
        if profit_table[ending] == None or tmp - e > profit_table[ending]:
            profit_table[ending] = tmp - e
    return profit_table

def get_final(ar):
    mp1 = [0] * len(ar)
    mp2 = [0] * len(ar)
    for i in range(1, len(ar)):
        mp1 = get_max_profit(ar,mp1,0,i)
    for i in range(1, len(ar)-1):
        tmp_ar = ar[i:]
        tmp_mp = [0] * len(tmp_ar)
        for k in range(1,len(tmp_ar)):
            tmp_mp = get_max_profit(tmp_ar,tmp_mp,0,k)
        mp2[i] = max(tmp_mp)
    result_mp = [mp1[i]+mp2[i] for i in range(len(mp1))]
    return mp1, mp2, result_mp

if __name__ == 'main':
    ar = [1,2,1,2,3,4,5,2,9,4,6]
    results = get_final(ar) # is it a fxxking tough problem! goddamnit.

(2020.09.25 Fri)再次整理思路和數(shù)學(xué)模型
創(chuàng)建一個(gè)空序列g(shù)荸百，g的長度和s一樣闻伶。g保存的是序列中對應(yīng)元素與該元素前面的元素之差的最大值。數(shù)學(xué)表示 $g[i] = max(s[i] - s[i-k]), \space k=1,2,...,i-1$
這種情況下管搪，找出序列g(shù)的最大值虾攻，也就找出了只做一次買入+賣出操作可以獲得的最大收益铡买。

def get_max_list(arr):
    max_profit = [0]*len(arr)
    for i,e in enumerate(arr):
        if i == 0:
            continue
        max_profit[i] = max([e-term for term in arr[:i])
    return max_profit

if __name__ == '__main__':
    arr = [1,2,1,2,3,4,5,2,9,4,6]
    result = max(get_max_list(arr))

如果做兩次操作更鲁，分為兩個(gè)情況霎箍，情況1) 買賣操作是連續(xù)完成，也就是買入和賣出的動作之間沒有買入操作澡为，情況2) 兩次買入賣出的操作在時(shí)間軸上有重疊漂坏。

情況1
這種情況只需要把序列s分開成 $s_1$ 和 $s_2$ ，有 $s=s_1+s_2$ 媒至。假設(shè)序列s的長度是100顶别。
對于 $s_1$ 和 $s_2$ ，分別按照上面只買賣一次的操作計(jì)算最大收益拒啰，之后計(jì)算兩個(gè)最大收益之和驯绎。設(shè)s序列在某個(gè)點(diǎn)x被分開， $s_1 =s[1,x], \space s_2 = [x+1,100]$ 谋旦。分別計(jì)算對應(yīng)的 $g_1$ 和 $g_2$ 剩失。對于 $g_1$ 和 $g_2$ ，有 $g_1[i] = min(s_1[i]-s_1[i-k]), \space k = 1,2,...,i-1$
$g_2[i] = min(s_2[i]-s_2[i-k]), \space k = 1,2,...,i-1$
現(xiàn)在要求的是 $max( max(g_1) + max(g_2))$ 册着，最大值的求法只需要對分割點(diǎn)x做遍歷拴孤，x的取值范圍是2到99.

if __name__ == '__main__':
    arr = [3,2,1,4,5,6,7,5,4,3,2]
    result = None
    for i in range(2,len(arr)-2):
        max1 = get_max_list(arr[:i])
        max2 = get_max_list(arr[i:])
        if not result:
            result = max1 + max2
        elif result > max1 + max2:
            result = max1 + max2

情況2
也就是可以先買兩次，之后分別賣出甲捏。解決方案更加簡潔演熟，只需要對s序列做一次計(jì)算得到一個(gè)g序列，在g序列中找出兩個(gè)最大值即可司顿。 $max(g) + max(g.pop(max(g)))$

if __name__ == '__main__':
    arr = [3,2,1,4,5,6,7,5,4,3,2]
    tmp = get_max_list(arr)
    result1 = max(tmp)
    tmp.remove(result1)
    result2 = max(tmp)

(2020.09.13 Sun輸入, 2020.09.04筆記)
Case 6 加權(quán)圖的網(wǎng)絡(luò)芒粹，各edge上有weight，求從一點(diǎn)到另一點(diǎn)的path weight和的最小值和path
參考Floyd-Warshall算法大溜。

Case 7 從樓上扔雞蛋/鴕鳥蛋的問題
M層樓是辕，N個(gè)雞蛋，找出不碎的樓層猎提，最少需要幾次获三？（最壞情況下的代價(jià)最小）
(2020.09.17 Thur)

問題變種：給定樓層比如103層锨苏，給定雞蛋2顆疙教，求最壞情況下需要測幾次。
(這個(gè)解法來自2016.11.04的筆記)
遞歸解法：定義 $f(k)$ 是最多投下 $k$ 次雞蛋能達(dá)到樓層的最大值伞租，初始值 $f(1)=1$ 贞谓。定義最壞情況：可投 $k$ 次，第1次從 $n$ 層開始葵诈，雞蛋破裸弦，之后從第1層開始投另一個(gè)蛋祟同，之后是第2層 & so on，直到第 $(n-1)$ 層理疙。最優(yōu)的解法是設(shè) $n=k$ 晕城，從第 $k$ 層投下雞蛋完好，則可以用剩下的 $(k-1)$ 次測試更高樓層窖贤，此時(shí)能測試的最高層是 $f(k-1)+k$ 層砖顷，因此有遞歸式 $f(k)=f(k-1)+k$ 也就是 $f(k) = \sum_{i=1}^{k} i$
樓層是102，該數(shù)字位于 $f(13)=91$ 和 $f(14)=105$ 之間赃梧，因此最壞情況下需要投14次滤蝠。
M層樓，N個(gè)雞蛋授嘀，找出不碎的樓層的最少次數(shù)物咳。
動態(tài)規(guī)劃解法：設(shè)是最優(yōu)解法的最大嘗試次數(shù)。假設(shè)第一個(gè)雞蛋扔出的位置在第X層蹄皱，會出現(xiàn)兩種情況
- 第1個(gè)蛋沒碎览闰，則剩下 $M-X$ 層，剩 $N$ 個(gè)蛋夯接，轉(zhuǎn)變?yōu)橄旅姹磉_(dá)式 $F(M-X,N) + 1, \space where \space 1\leq X \leq M$
- 第1個(gè)蛋碎焕济，則剩下1層到 $X-1$ 層需要嘗試，剩下 $N-1$ 個(gè)蛋盔几，轉(zhuǎn)變?yōu)橄旅姹磉_(dá)式 $F(X-1, N-1) + 1, \space where \space 1\leq X \leq M$
  整體而言需要找到最大嘗試次數(shù)的最小解晴弃，則轉(zhuǎn)移方程可以表示成如下形式 $F(M,N) = min( max( F(M-X,N) + 1, F(X-1,N-1) + 1) )$

def egg_dropping(m, n):
    if m == 0: return 0
    if n == 1: return m
    res = min([max(egg_dropping(i-1,n-1),egg_dropping(m-i,n))  for i in range(1,m+1)])+ 1
    return res

策略分析：假定雞蛋個(gè)數(shù)超過1，第一次在第 $n$ 層扔雞蛋逊拍，之后每次扔的層數(shù)會在上次的層數(shù)加某個(gè)值上鞠，該值大于1在有超過1一個(gè)雞蛋的時(shí)候⌒旧ィ可以想象到芍阎，隨著每次扔的層數(shù)提高，雞蛋破碎的概率應(yīng)該越來越大(假定最終一定會碎)缨恒，因此大概應(yīng)該有每次增加的層數(shù)可能會比上次增大的層數(shù)小谴咸。故可以隨著扔的次數(shù)上升，在沒到最后一個(gè)雞蛋時(shí)骗露，每次扔的層數(shù)增量減少岭佳。策略細(xì)節(jié)，不是太懂萧锉。

(2020.09.21 Mon
Case 8 The Coin Change Problem硬幣零錢問題
原題在這里珊随。
有若干種硬幣面值，給定一個(gè)數(shù)字，求有多少種硬幣的取法叶洞。比如硬幣面值(2,3,5,6)鲫凶，數(shù)字10代表需要取的總值，則取法有(2,2,2,2,2)衩辟，(2,2,6)螟炫，(2,2,3,3)，(5,5)惭婿，(2,3,5)不恭，共5種取法叶雹。注意計(jì)算過程中按每種硬幣遍歷财饥，再按1到總值遍歷。切忌不要先遍歷1到總值折晦，再遍歷硬幣面值钥星，因?yàn)檫@種遍歷方法會重復(fù)計(jì)算，例如 $f(5)=f(3)+f(2)$ 满着，總值為5時(shí)只有一種取法(2,3)谦炒，但是此種遍歷會把(2,3)和(3,2)當(dāng)做兩種取法，這種遍歷方式適合計(jì)算排列的個(gè)數(shù)风喇，比如青蛙跳井的方式有多少種宁改。針對這個(gè)問題，需要先從小打到遍歷硬幣面值魂莫，比如從2開始計(jì)算还蹲，得到的 $f(i)$ 是只用面值2得到多少種取法，之后計(jì)算面值3耙考，得到的是用面值2和3得到多少種取法谜喊，之后計(jì)算面值5，得到的 $f(i)$ 是用2倦始，3斗遏，5三種面值得到的取法，以此類推鞋邑。這種遍歷方式可以避免前面提到的計(jì)算排列诵次，而是計(jì)算有多少種組合。

def get_combinations(n,c):
    # n: the value, c: the list of coin denomination
    c = sorted(c)
    res = [0] * (n+1) # the list of ways
    for deno in c:
        for i in range(1,n+1):
            if deno > i: 
                continue # denomination is bigger than value, simply skip
            elif deno == i:
                res[i] += 1 # deno is the very value, add 1
            else:
                res[i] += res[i-deno] 
    return res[-1]

Case 8.1 青蛙跳井
每天跳1步或者2步枚碗，隨機(jī)逾一，一個(gè)井深10步，有多少種跳法视译？注意嬉荆，相鄰的兩天分別跳1步2步和2步1步代表著兩種跳法。
考慮上面的分析酷含，這種情況需要從深度遍歷鄙早，再從步數(shù)遍歷汪茧。

def get_permutation(n,c):
    # n: well depth, c: the list of possible steps
    c = sorted(c)
    res = [0] * (n+1) # the list of ways
    for i in range(1,n+1):
        for step in c:
            if step > i: 
                break # step is bigger than depth, simply skip
            elif step == i:
                res[i] += 1 # step is the very value, add 1
            else:
                res[i] += res[i-step] 
    return res

(2020.09.26 Sat)
Case 9 戳氣球
有n個(gè)氣球形成一個(gè)序列b，編號從0到n-1限番，每個(gè)氣球上對應(yīng)了一個(gè)數(shù)字舱污，但該數(shù)字不是氣球的編號。現(xiàn)在戳破所有氣球弥虐，如果從i開始戳扩灯，則可以獲得 $b[i]*b[left]*b[right]$ 個(gè)硬幣，注意 $b[i],b[left],b[right]$ 是氣球上的數(shù)字霜瘪，而 $b[left],b[right]$ 是緊鄰氣球i的沒有被戳破的最近的兩個(gè)氣球珠插。求可以獲得的最大硬幣數(shù)量。
Notes:

假定b的0之前的元素和n-1之后的元素都是1颖对，也就是b左右各補(bǔ)充一個(gè)元素捻撑，且都為1.
n<=500，max(b[i]) <= 100

思路：(該方法由labuladong提供)
如果和前面案例不同的是缤底，該題目中每個(gè)子問題都由前一步的結(jié)果決定顾患，因此子問題不夠獨(dú)立。需要選好建模角度个唧。
對序列b的左右兩端加上端點(diǎn)也就是兩個(gè)1江解，長度由n變?yōu)閚+2，原題目變?yōu)橐粋€(gè)長度為n+2的序列徙歼，只戳破序號1到序號n的部分犁河，可以獲得的最大硬幣數(shù)目。設(shè)d[i][j]是戳破i到j(luò)之間的氣球可以獲得的最大硬幣數(shù)鲁沥，故此題可以變?yōu)榍骴[0][n+2]的值呼股。
進(jìn)一步，設(shè)k是i到中j最后一個(gè)被戳破的點(diǎn)画恰，有 $d[i][j] = d[i][k] + d[k][j] + b[i]*b[k]*b[j],\space i < k < j$ 彭谁。一個(gè)初始條件是 $d[i][i]=0$ ，從條件出發(fā)即可代碼實(shí)現(xiàn)允扇。代碼略缠局。

Case 10 博弈問題取石頭
有一排石頭堆，用一個(gè)數(shù)組 piles 表示考润，piles[i] 表示第 i 堆石子有多少個(gè)狭园。兩個(gè)人輪流拿石頭，一次拿一堆糊治，但是只能拿走最左邊或者最右邊的石頭堆唱矛。所有石頭被拿完后，誰擁有的石頭多，誰獲勝绎谦。假設(shè)兩人都很聰明管闷，請?jiān)O(shè)計(jì)一個(gè)算法，返回先手和后手的最后得分（石頭總數(shù)）之差窃肠。
思路：(該方法由labuladong提供)
該問題建陌觯可根據(jù)先手后手建模。d[i][j].fir和d[i][j].sec分別表示從i到j(luò)的piles中冤留，先手和后手可以獲得的最高分?jǐn)?shù)碧囊。問題歸結(jié)為計(jì)算出 $abs(d[0][n-1].fir - d[0][n-1].sec)$ 。每個(gè)人只能從piles的左側(cè)或者右側(cè)選擇石頭纤怒，并且每個(gè)人都聰明要保證自己的石頭最多糯而。先手選擇石頭之后，就變成了后手肪跋，而后手在對方做完選擇之后就變成了先手歧蒋，角色的轉(zhuǎn)換可以重用之前的結(jié)果土砂，是動態(tài)規(guī)劃的應(yīng)用場景州既。因此模型可以表示為 $d[i][j].fir = max(p[i]+d[i+1][j].sec, \space p[j]+d[i][j-1].sec)$
$d[i][j].sec = max(p[i]+d[i+1][j].fir, \space p[j]+d[i][j-1].fir)$
有初始條件 $d[i][i].fir = piles[i], \space d[i][i].sec = 0$ 。
算法實(shí)現(xiàn)時(shí)從d矩陣的對角線和其兩側(cè)開始實(shí)現(xiàn)萝映。

Case 11 過橋問題
夜里n個(gè)人過橋從起點(diǎn)A到橋?qū)γ鍮吴叶，橋窄每次最多兩人通過，手電只有一個(gè)序臂，沒手電不能過橋蚌卤。每個(gè)人過橋時(shí)間不同，兩個(gè)人同時(shí)過橋的時(shí)間由兩個(gè)人中時(shí)間比較長的決定奥秆。問n個(gè)人最快需要多久全都過橋逊彭？
思路：用t[i]代表i個(gè)人已經(jīng)過橋用的最短時(shí)間，用序列p代表從大到小的個(gè)人過橋時(shí)間构订，即p[1]最小侮叮，p[n]最大。當(dāng)A只剩一個(gè)人的時(shí)候悼瘾，需要在B的 $(n-1)$ 個(gè)人里面過橋時(shí)間最短的人把手電送過來囊榜，并且和最后一個(gè)人一同過橋。假設(shè)p[n]是最后一個(gè)人亥宿，則有 $t[n] = t[n-1] + p[1] + p[n]$ 卸勺。
當(dāng)A端剩最后兩個(gè)人時(shí)，需要過橋時(shí)間短的人把手電送過來烫扼，A端的兩個(gè)人拿著手電同時(shí)過橋曙求，再由B端的人里面過橋時(shí)間最短的把手電送過來，和A端剩下的那個(gè)人同時(shí)過橋，過橋時(shí)間由這兩人里面比較長的那個(gè)人決定悟狱。假設(shè)在 $(n-2)$ 個(gè)人過橋之后怎抛，留下了p[n]和p[n-1]在A，過橋時(shí)間最短的兩個(gè)人時(shí)p[1]和p[2]芽淡，此時(shí)1和2誰來送手電都可马绝。當(dāng)只剩最后一個(gè)人時(shí)，1和2中在B的人送手電過去挣菲，兩人再同時(shí)過橋完成輸送富稻，有 $t[n] = t[n-2] + p[n] + p[1] + 2\times p[2]$ 。結(jié)合這兩種情況白胀，得到一個(gè)最終的表達(dá)式 $t[n] = min(t[n-1]+p[1]+p[n], t[n-2]+p[n]+p[1]+2\times p[2])$ 椭赋。初始條件 $t[1]=p[1],\space t[2]=p[2]$ 。
這種解答的假設(shè)是過的慢的后過橋或杠。

用貪婪的思路得到的方案不是最優(yōu)哪怔，過橋時(shí)都是 $p[1]$ 陪著 $p[i], \space i > 1$ 過橋， $p[1]$ 回來送手電向抢。但是經(jīng)過計(jì)算认境，得到的總過橋時(shí)間會長于前面動態(tài)規(guī)劃。

動態(tài)規(guī)劃

def get_min(arr):
    arr = sorted(arr)
    t = [0] * len(arr)
    t[0],t[1]=arr[0],arr[1]
    for i in range(2,len(arr)):
        t[i] = min(t[i-1]+arr[0]+arr[i], t[i-2]+arr[i]+arr[0]+2*arr[1])
    return t

if __name__ == '__main__':
    arr = [7,4,9,3,5,1,2]
    res = get_min(arr)
    print(res[-1])

(2020.09.28 Mon)
Case 12 硬幣頭像期望問題
硬幣均勻挟鸠，分為頭像和數(shù)字兩面叉信，拋硬幣兩面分別有50%的概率。求連續(xù)5次得到同一面A需要拋次數(shù)的期望艘希。
分析：設(shè) $e(n)$ 是連續(xù)拋出n次A面時(shí)拋次數(shù)的期望硼身。當(dāng)連續(xù)出現(xiàn) $(n-1)$ 次A面時(shí)，下一步可能出現(xiàn)兩種情況覆享，即A或B佳遂，各有50%概率。當(dāng)與上一次的面相反撒顿，則截止到第 $(n-1)$ 次連續(xù)得到A面之前的所有拋次數(shù)都無效丑罪，且之后的一次B面也無效，需要重新計(jì)算核蘸。于是有 $e(n) = 0.5 \cdot (e(n-1)+1) + 0.5 \cdot (e(n-1) + 1 + e(n))$
$e(n) = 2\cdot e(n-1) +2$ 推導(dǎo)得到 $e(n) = e(1)^{n+1}-2$ 巍糯。
下面計(jì)算 $e(1)$ 。 $e(1)$ 代表著拋出1次A面需要的拋次數(shù)期望客扎。有可能第一次就拋出A面祟峦，或者前面 $(n-1)$ 次都是B面，到了第 $n$ 次是A面徙鱼≌悖可根據(jù)這個(gè)分析求得 $e(1) = 1\cdot\frac{1}{2} (此項(xiàng)代表第一次即A面)+2\cdot (\frac{1}{2})^2 (第二次是A面) + 3 \cdot (\frac{1}{2})^3(第三次是A面)+\dots$
$e(1) = \sum_{n=1}n(\frac{1}{2})^n$
有
$2e(1) = 2\sum_{n=1}n(\frac{1}{2})^n=\sum_{n=1}(n-1+1)(\frac{1}{2})^{n-1}=\sum_{n=1}(n-1)(\frac{1}{2})^{n-1}+\sum_{i=1}(\frac{1}{2})^{n-1}$ 其中的 $\sum_{n=1}(n-1)(\frac{1}{2})^{n-1} = e(1)$ 针姿，而 $\sum_{i=1}(\frac{1}{2})^{n-1}=2$ ，于是有 $2e(1) = e(1) + 2$ 厌衙， $e(1) = 2$ 距淫，所以 $e(n) = 2^{n+1} -2$ 。

(2020.10.18 Sun)
Case 13 一個(gè)箱子里有N個(gè)球婶希，每次取一個(gè)球并放回去榕暇，求每個(gè)球都被取出一次的期望。
該思路類似于動態(tài)規(guī)劃喻杈。設(shè) $E(i)$ 表示有 $i$ 個(gè)球被取出過的條件下取出其他球還需要多少次彤枢。取到了一個(gè)被取過的球，需要的次數(shù)期望是 $\frac{i}{N} \cdot (1 + E(i))$ 筒饰；取到了一個(gè)沒有被取過的球缴啡，需要的次數(shù)期望是 $(1- \frac{i}{N}) \cdot (1 +E(i+1))$ 。因此有 $E(i) = \frac{i}{N} \cdot (1 + E(i)) + (1-\frac{i}{N}) \cdot (1 +E(i+1))$
$E(i) = \frac{N}{N-i} + E(i+1)$
初始條件瓷们， $E(N) = 0$ 业栅， $E(N-1) = N, \space E(N-2) = N+ \frac{N}{2}, \space E(N-3) = N + \frac{N}{2} + \frac{N}{3}$
$E(0) = N \cdot \sum_{i=1}^{N} \frac{1}{i}$
Case 13-1：一個(gè)骰子拋出所有點(diǎn)數(shù)的期望次數(shù)是多少？
根據(jù)Case 13推出的公式可以算出結(jié)果谬晕。

幾個(gè)供學(xué)習(xí)的文章
1 DP總結(jié)
2 DP各種子序列問題
3 什么是動態(tài)規(guī)劃

reference:
1 M.T. Goodrich, Data Structures and Algorithms in Python
2 劉汝佳碘裕，算法競賽入門經(jīng)典(第2版)
3 漫畫：動態(tài)規(guī)劃解決扔雞蛋問題
4 動態(tài)規(guī)劃經(jīng)典問題：高樓扔雞蛋
5 高樓扔雞蛋進(jìn)階解法
6 高樓扔雞蛋問題動態(tài)規(guī)劃大法
7 扔雞蛋的論文
8 知乎扔雞蛋
9 量化面試
10 一篇搞定動態(tài)規(guī)劃常考算法題固蚤，微信公眾號娘汞，路人zhang

最后編輯于：2022.09.23 12:15:51

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市夕玩，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌惊豺，老刑警劉巖燎孟，帶你破解...
沈念sama閱讀 217,509評論 6贊 504
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異尸昧，居然都是意外死亡揩页，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,806評論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門烹俗，熙熙樓的掌柜王于貴愁眉苦臉地迎上來爆侣，“玉大人，你說我怎么就攤上這事幢妄⊥醚觯” “怎么了？”我有些...
開封第一講書人閱讀 163,875評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵蕉鸳，是天一觀的道長乎赴。經(jīng)常有香客問我忍法，道長，這世上最難降的妖魔是什么榕吼？我笑而不...
開封第一講書人閱讀 58,441評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任饿序，我火速辦了婚禮，結(jié)果婚禮上羹蚣，老公的妹妹穿的比我還像新娘原探。我一直安慰自己，他們只是感情好顽素，可當(dāng)我...
茶點(diǎn)故事閱讀 67,488評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布踢匣。她就那樣靜靜地躺著，像睡著了一般戈抄。火紅的嫁衣襯著肌膚如雪离唬。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,365評論 1贊 302
城市分裂傳說
那天划鸽，我揣著相機(jī)與錄音输莺，去河邊找鬼。笑死裸诽，一個(gè)胖子當(dāng)著我的面吹牛嫂用，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播丈冬，決...
沈念sama閱讀 40,190評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼嘱函，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了埂蕊？” 一聲冷哼從身側(cè)響起往弓，我...
開封第一講書人閱讀 39,062評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎蓄氧，沒想到半個(gè)月后函似，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,500評論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡喉童，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,706評論 3贊 335
?白月光啟示錄
正文我和宋清朗相戀三年撇寞，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片堂氯。...
茶點(diǎn)故事閱讀 39,834評論 1贊 347
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡蔑担，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出咽白，到底是詐尸還是另有隱情啤握，我是刑警寧澤，帶...
沈念sama閱讀 35,559評論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布局扶，位于F島的核電站恨统，受9級特大地震影響叁扫，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜畜埋，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,167評論 3贊 328
男人毒藥：我在死后第九天來索命
文/蒙蒙一莫绣、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧悠鞍，春花似錦对室、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,779評論 0贊 22
一樁弒父案掩宜，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至么翰，卻和暖如春牺汤，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背浩嫌。一陣腳步聲響...
開封第一講書人閱讀 32,912評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工檐迟，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人码耐。一個(gè)月前我還...
沈念sama閱讀 47,958評論 2贊 370
代替公主和親
正文我出身青樓追迟，卻偏偏與公主長得像，于是被迫代替她去往敵國和親骚腥。傳聞我的和親對象是個(gè)殘疾皇子敦间，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,779評論 2贊 354

動態(tài)規(guī)劃Dynamic programming, since 2020-04-26

解決的問題類型

問題特征

典型問題

推薦閱讀更多精彩內(nèi)容