动态规划Dynamic programming, since 2

作者: Mc杰夫 | 来源:发表于2020-04-26 22:41 被阅读0次

DP是用途广泛的问题解决思路/思想，而不是特定的算法。主要用于优化问题(optimisation)，求解最优方法。如果待解决的问题有如下特性，则适用于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 solutions.
Subproblem overlap子问题混叠: Optimal solutions to unrelated subproblems can contain subproblems in common.

(2020.09.13 Sun输入，2020.09.04笔记)

解决的问题类型

求最大/小值
方案是否可行
方案的总数
注意: 求所有方案和结果的具体内容，可能无法使用DP。

问题特征

递归+重复，具体来说符合[一个模型三个特征]。

模型
多阶段决策最优解模型
特征
- 最优子结构，即每个阶段都有最优解
- 无后效性，当前阶段最优解仅与上个阶段最优解有关，不在乎上个阶段最优解如何得出
- 重复子问题，自下而上的方式有重复子问题。比如，一个8 * 8的格子，每次向右/下走一步，有多少种走法？相当于第一次从顶点向右或下，走到一个7 * 7的格子，and so on.设左上角的点是(0,0)右下角的点(7,7)，起点的位置是(x,y)，#path(x,y) = #path(x+1,y) + #path(x,y+1)
- 子问题间保持独立，也可理解为无后效性

(2020.09.13 Sun输入，2020.09.04笔记)

典型问题

背包问题backpack
资源分配
区间模型
树型模型

背包问题：类似的问题有青蛙跳井问题和取硬币问题。以价值为状态。背包的详细分解见背包九讲。只看简单的背包问题0-1背包。有一个背包和n个物品，每个物品只有一个，其重量(或价值)为 $W_i$ ，其体积 $V_i$ ，包的总体积 $V$ ，求如何取物品保证包装的足够满，且总重量最大。
d(i,j)表示把第i, i+1, i+2, ...n个物品放在容量为j的背包中的最大总重量，或者当前在第i层，背包剩余容量为j时接下来的最大重量和，有 $d(i,j)= max(d(i+1,j),\space d(i+1,j-V_i)-W_i)$ 。边界条件 $i>n$ ，则 $d(i,j)=0$ 。
资源分配：类似的有花店橱窗布置和马厩问题。有m个资源，分给n个部分，第i个部门获得j资源时有盈利值v(i,j)，如何分配使得盈利最大？最大是多少？
设f(i,j)表示前 $i$ 个部门分配 $j$ 个资源时获得的最大盈利，可拆分为前 $i-1$ 个部门分配 $k$ 个资源和第 $i$ 个部门分配 $j-k$ 个资源，通过遍历 $k$ 可以找到最大盈利。有 $f(i,j) = max(f(i-1,k) + v(i,j-k)), 0\leq k \leq j$ 。
区间模型：参考LIS/LCS/回文串的cases。

Case 1 Matrix chain-product矩阵连乘积:
（2020.04.26）
这个问题里我们关注矩阵chain-product的计算量。
$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$ 。注意到矩阵乘法可以使用乘法结合律，即 $B \cdot (C \cdot D) = (B \cdot C) \cdot D$ 。
设 $B$ 的尺寸为 $2\times10$ ， $C$ 的尺寸为 $10\times50$ ， $D$ 的尺寸为 $50\times20$ 。采用 $B \cdot (C \cdot D)$ 的方式计算，总计算次数为
$10\times50\times20(这是C\times D的次数)+2\times10\times20(这是B\times C、D相乘的结果的次数)=10400$

采用 $(B\times C)\times D$ 的方式计算，总计算次数为
$2\times10\times50(这是B\times C计算的次数)+2\times 50 \times 20(这是B、C相乘的结果与D相乘的次数)=3000$

由此可见parenthesisation对于矩阵连乘积的运算量影响显著。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)
首先确认该问题可以分解为子问题，即to compute the best parenthesisation for some subexpression $A_{i} \cdot A_{i+1} \cdots A_{j}$ 。定义 $N_{i,j}$ 为该表达式最少乘法次数。因此初始问题可以转化为计算 $N_{0,n-1}$ 。
解决子问题
一个观察的结论: 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}$ 。问题转化为计算 $N_{i,j}$ 在不同 $k$ 位置取得的最小值。
设计动态规划算法
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}$ 的计算量/计算次数， $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}$ 中，前一项 $A_{i}\times A_{i+1}\times \cdots A_{k}$ 的运算次数是 $N_{i,k}$ ，后一项 $A_{i}\times A_{k+1}\times \cdots A_{j}$ 的运算次数是 $N_{k+1,j}$ 。前一项的尺寸是 $d_{i}d_{k+1}$ ，后一项的尺寸是 $d_{k+1}d_{j+1}$ ，因此前后两项相乘的运算次数是 $d_{i}d_{k+1}d_{j+1}$ 。于是可以用bottom-up fashion来计算 $N_{i,j}$ ，从0开始生成一个表，存储 $N_{i,j}$ 的所有值。对任意非负整数 $i$ ，有初始条件 $N_{i,i}=0$ 。由 $N_{i,j}$ 的公式和初始条件，可求得 $N_{i,i+1}$ ，并由 $N_{i,i+1}$ 可推得 $N_{i,i+2}$ ，进而推得 $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)
问题源自两类实际问题，即比较序列的相似性(i.e., DNA/代码)。
Subsequence子序列: 从原序列中抽取，并按原有顺序排列的序列，未必contiguous连续抽取。如 $CTAG$ 是 $\underline{C}GATAA\underline{T}TG\underline{AG}A$ 的子序列。

Longest Common Subsequence (LCS)最长共同子序列
问题描述：给定两个序列 $X=x_0x_1\cdots x_{n-1}$ 和 $Y=y_0y_1\cdots y_{m-1}$ ，找出同时为 $X$ 和 $Y$ 的子序列中最长的一个。
Brute-force approach: 列举出 $X$ (长度为 $n$ )的所有子序列，共计 $2^{n}$ 个，逐个判断是否为 $Y$ (长度为 $m$ )的子序列，每次判断的时间复杂度 $O(m)$ ，因此总的时间复杂度为 $O(2^{n}m)$ ，效率低下。而用动态规划有如下解决方案。
(2020.04.29 Wed)
DP方案用于优化问题，即寻找"最好的"解决方案。如果问题有如下特性，则可以用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寻址两个字符串 $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$ 。这种定义方式可根据子问题重写 $L_{j,k}$ 。针对 $L_{10,12}$ 考虑下面两种情况:

两个子序列的最后一位相同，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}.$
两个子序列的最后一位不同，此时两个序列的common subsequence不能同时包含 $X[9]$ 和 $Y[11]$ ，也就是其common subsequence或者以 $X[9]$ 结尾或者以 $Y[11]$ 结尾，或者不以其中任一个结尾，但一定不会是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}$ 的定义满足子问题优化，也使用了子问题重叠。用 $L_{j,k}$ 设计DP算法非常直接，设 $0 \le j \le n, 0 \le k \le m$ ，创建一个 $(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

复杂度: $O(nm)$ .
lcs函数求出了LCS的长度，但不是LCS的序列，下面这个函数可以求得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))

复杂度: $O(n+m)$ .

(2020.09.13 Sun输入，2020.09.10笔记)
Case 3 Longest Increasing Sequence LIS 最长上升序列
求一个序列中的最长上升序列有多长。序列s中任一个index对应的最长上升序列长度是f(i)，有 $f(i) = max(f(j))+1, i>j \space and \space s[i]>s[j]$
复杂度 $O(n^2)$

Case 4 回文串(palindrome)两个问题

一个字符串中palindrome的最长长度，2) 如果不是回文串，最少加多少可以成为一个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$ 。当 $s[i]=s[i+1]$ ，有 $f[i][i+1]=2$ ，当 $s[i]!=s[j]$ ，有 $f[i][i+1] = 1$ 。
最少加入多少个字符可以成为palindrome。序列s中的s[i,...j] (i<j)部分需要加入最少d[i][j]个字符串能够成为palindrome，当 $s[i]=s[j]$ ，有 $d[i][j]=d[i+1][j-1]$ 。当 $s[i]!=s[j]$ ，有 $d[i][j] = min(d[i+1][j],d[i][j-1])+1$

(2020.09.03 Thur)
Case 5 (rt对冲面试) 一个数组(长度n)代表了是一个股价的时间序列，可按照这个序列中的价格买入或卖出。如果最多可以进行两次买入卖出操作，计算在该时间序列中可获得的最大收益。
思路：第一步计算index从0到i的序列中从0到每个index做一次买入卖出操作可获得的最大收益mp1。第二步，计算从i+1到结尾(n-1)的序列中从i+1开始到每个index做一次买入卖出操作可获得的最大收益mp2。第三步，i遍历从0到n-1，计算 $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)再次整理思路和数学模型
创建一个空序列g，g的长度和s一样。g保存的是序列中对应元素与该元素前面的元素之差的最大值。数学表示 $g[i] = max(s[i] - s[i-k]), \space k=1,2,...,i-1$
这种情况下，找出序列g的最大值，也就找出了只做一次买入+卖出操作可以获得的最大收益。

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))

如果做两次操作，分为两个情况，情况1) 买卖操作是连续完成，也就是买入和卖出的动作之间没有买入操作，情况2) 两次买入卖出的操作在时间轴上有重叠。

情况1
这种情况只需要把序列s分开成 $s_1$ 和 $s_2$ ，有 $s=s_1+s_2$ 。假设序列s的长度是100。
对于 $s_1$ 和 $s_2$ ，分别按照上面只买卖一次的操作计算最大收益，之后计算两个最大收益之和。设s序列在某个点x被分开， $s_1 =s[1,x], \space s_2 = [x+1,100]$ 。分别计算对应的 $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$
现在要求的是 $max( max(g_1) + max(g_2))$ ，最大值的求法只需要对分割点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序列做一次计算得到一个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 加权图的网络，各edge上有weight，求从一点到另一点的path weight和的最小值和path
参考Floyd-Warshall算法。

Case 7 从楼上扔鸡蛋/鸵鸟蛋的问题
M层楼，N个鸡蛋，找出不碎的楼层，最少需要几次？（最坏情况下的代价最小）
(2020.09.17 Thur)

问题变种：给定楼层比如103层，给定鸡蛋2颗，求最坏情况下需要测几次。
(这个解法来自2016.11.04的笔记)
递归解法：定义 $f(k)$ 是最多投下 $k$ 次鸡蛋能达到楼层的最大值，初始值 $f(1)=1$ 。定义最坏情况：可投 $k$ 次，第1次从 $n$ 层开始，鸡蛋破，之后从第1层开始投另一个蛋，之后是第2层 & so on，直到第 $(n-1)$ 层。最优的解法是设 $n=k$ ，从第 $k$ 层投下鸡蛋完好，则可以用剩下的 $(k-1)$ 次测试更高楼层，此时能测试的最高层是 $f(k-1)+k$ 层，因此有递归式 $f(k)=f(k-1)+k$ 也就是 $f(k) = \sum_{i=1}^{k} i$
楼层是102，该数字位于 $f(13)=91$ 和 $f(14)=105$ 之间，因此最坏情况下需要投14次。
M层楼，N个鸡蛋，找出不碎的楼层的最少次数。
动态规划解法：设是最优解法的最大尝试次数。假设第一个鸡蛋扔出的位置在第X层，会出现两种情况
- 第1个蛋没碎，则剩下 $M-X$ 层，剩 $N$ 个蛋，转变为下面表达式 $F(M-X,N) + 1, \space where \space 1\leq X \leq M$
- 第1个蛋碎，则剩下1层到 $X-1$ 层需要尝试，剩下 $N-1$ 个蛋，转变为下面表达式 $F(X-1, N-1) + 1, \space where \space 1\leq X \leq M$
  整体而言需要找到最大尝试次数的最小解，则转移方程可以表示成如下形式 $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

策略分析：假定鸡蛋个数超过1，第一次在第 $n$ 层扔鸡蛋，之后每次扔的层数会在上次的层数加某个值，该值大于1在有超过1一个鸡蛋的时候。可以想象到，随着每次扔的层数提高，鸡蛋破碎的概率应该越来越大(假定最终一定会碎)，因此大概应该有每次增加的层数可能会比上次增大的层数小。故可以随着扔的次数上升，在没到最后一个鸡蛋时，每次扔的层数增量减少。策略细节，不是太懂。

(2020.09.21 Mon
Case 8 The Coin Change Problem硬币零钱问题
原题在这里。
有若干种硬币面值，给定一个数字，求有多少种硬币的取法。比如硬币面值(2,3,5,6)，数字10代表需要取的总值，则取法有(2,2,2,2,2)，(2,2,6)，(2,2,3,3)，(5,5)，(2,3,5)，共5种取法。注意计算过程中按每种硬币遍历，再按1到总值遍历。切忌不要先遍历1到总值，再遍历硬币面值，因为这种遍历方法会重复计算，例如 $f(5)=f(3)+f(2)$ ，总值为5时只有一种取法(2,3)，但是此种遍历会把(2,3)和(3,2)当做两种取法，这种遍历方式适合计算排列的个数，比如青蛙跳井的方式有多少种。针对这个问题，需要先从小打到遍历硬币面值，比如从2开始计算，得到的 $f(i)$ 是只用面值2得到多少种取法，之后计算面值3，得到的是用面值2和3得到多少种取法，之后计算面值5，得到的 $f(i)$ 是用2，3，5三种面值得到的取法，以此类推。这种遍历方式可以避免前面提到的计算排列，而是计算有多少种组合。

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步，随机，一个井深10步，有多少种跳法？注意，相邻的两天分别跳1步2步和2步1步代表着两种跳法。
考虑上面的分析，这种情况需要从深度遍历，再从步数遍历。

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个气球形成一个序列b，编号从0到n-1，每个气球上对应了一个数字，但该数字不是气球的编号。现在戳破所有气球，如果从i开始戳，则可以获得 $b[i]*b[left]*b[right]$ 个硬币，注意 $b[i],b[left],b[right]$ 是气球上的数字，而 $b[left],b[right]$ 是紧邻气球i的没有被戳破的最近的两个气球。求可以获得的最大硬币数量。
Notes:

假定b的0之前的元素和n-1之后的元素都是1，也就是b左右各补充一个元素，且都为1.
n<=500，max(b[i]) <= 100

思路：(该方法由labuladong提供)
如果和前面案例不同的是，该题目中每个子问题都由前一步的结果决定，因此子问题不够独立。需要选好建模角度。
对序列b的左右两端加上端点也就是两个1，长度由n变为n+2，原题目变为一个长度为n+2的序列，只戳破序号1到序号n的部分，可以获得的最大硬币数目。设d[i][j]是戳破i到j之间的气球可以获得的最大硬币数，故此题可以变为求d[0][n+2]的值。
进一步，设k是i到中j最后一个被戳破的点，有 $d[i][j] = d[i][k] + d[k][j] + b[i]*b[k]*b[j],\space i < k < j$ 。一个初始条件是 $d[i][i]=0$ ，从条件出发即可代码实现。代码略。

Case 10 博弈问题取石头
有一排石头堆，用一个数组 piles 表示，piles[i] 表示第 i 堆石子有多少个。两个人轮流拿石头，一次拿一堆，但是只能拿走最左边或者最右边的石头堆。所有石头被拿完后，谁拥有的石头多，谁获胜。假设两人都很聪明，请设计一个算法，返回先手和后手的最后得分（石头总数）之差。
思路：(该方法由labuladong提供)
该问题建模可根据先手后手建模。d[i][j].fir和d[i][j].sec分别表示从i到j的piles中，先手和后手可以获得的最高分数。问题归结为计算出 $abs(d[0][n-1].fir - d[0][n-1].sec)$ 。每个人只能从piles的左侧或者右侧选择石头，并且每个人都聪明要保证自己的石头最多。先手选择石头之后，就变成了后手，而后手在对方做完选择之后就变成了先手，角色的转换可以重用之前的结果，是动态规划的应用场景。因此模型可以表示为 $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$ 。
算法实现时从d矩阵的对角线和其两侧开始实现。

Case 11 过桥问题
夜里n个人过桥从起点A到桥对面B，桥窄每次最多两人通过，手电只有一个，没手电不能过桥。每个人过桥时间不同，两个人同时过桥的时间由两个人中时间比较长的决定。问n个人最快需要多久全都过桥？
思路：用t[i]代表i个人已经过桥用的最短时间，用序列p代表从大到小的个人过桥时间，即p[1]最小，p[n]最大。当A只剩一个人的时候，需要在B的 $(n-1)$ 个人里面过桥时间最短的人把手电送过来，并且和最后一个人一同过桥。假设p[n]是最后一个人，则有 $t[n] = t[n-1] + p[1] + p[n]$ 。
当A端剩最后两个人时，需要过桥时间短的人把手电送过来，A端的两个人拿着手电同时过桥，再由B端的人里面过桥时间最短的把手电送过来，和A端剩下的那个人同时过桥，过桥时间由这两人里面比较长的那个人决定。假设在 $(n-2)$ 个人过桥之后，留下了p[n]和p[n-1]在A，过桥时间最短的两个人时p[1]和p[2]，此时1和2谁来送手电都可。当只剩最后一个人时，1和2中在B的人送手电过去，两人再同时过桥完成输送，有 $t[n] = t[n-2] + p[n] + p[1] + 2\times p[2]$ 。结合这两种情况，得到一个最终的表达式 $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]$ 。
这种解答的假设是过的慢的后过桥。

用贪婪的思路得到的方案不是最优，过桥时都是 $p[1]$ 陪着 $p[i], \space i > 1$ 过桥， $p[1]$ 回来送手电。但是经过计算，得到的总过桥时间会长于前面动态规划。

动态规划

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 硬币头像期望问题
硬币均匀，分为头像和数字两面，抛硬币两面分别有50%的概率。求连续5次得到同一面A需要抛次数的期望。
分析：设 $e(n)$ 是连续抛出n次A面时抛次数的期望。当连续出现 $(n-1)$ 次A面时，下一步可能出现两种情况，即A或B，各有50%概率。当与上一次的面相反，则截止到第 $(n-1)$ 次连续得到A面之前的所有抛次数都无效，且之后的一次B面也无效，需要重新计算。于是有 $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$ 推导得到 $e(n) = e(1)^{n+1}-2$ 。
下面计算 $e(1)$ 。 $e(1)$ 代表着抛出1次A面需要的抛次数期望。有可能第一次就抛出A面，或者前面 $(n-1)$ 次都是B面，到了第 $n$ 次是A面。可根据这个分析求得 $e(1) = 1\cdot\frac{1}{2}(此项代表第一次即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 一个箱子里有N个球，每次取一个球并放回去，求每个球都被取出一次的期望。
该思路类似于动态规划。设 $E(i)$ 表示有 $i$ 个球被取出过的条件下取出其他球还需要多少次。取到了一个被取过的球，需要的次数期望是 $\frac{i}{N} \cdot (1 + E(i))$ ；取到了一个没有被取过的球，需要的次数期望是 $(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：一个骰子抛出所有点数的期望次数是多少？
根据Case 13推出的公式可以算出结果。