CLRS 15.3动态规划原理

15.3-1
运行RECURSIVE-MATRIX-CHAIN更高效一点。
第15.2节指出枚举所有可能的括号化方案是 $\Omega(4^n/n^{3/2})$。下面证明RECURSIVE-MATRIX-CHAIN是 $O(n3^{n-1})$。
书中的本节证明了：

$$T(n)=O(1)+\sum_{k=1}^{n-1}(T(k)+T(n-k)+O(1))$$
我们证明存在 $c$使得 $$T(n)\le c+\sum_{k=1}^{n-1}(T(k)+T(n-k)+c)= 2\sum_{i=1}^{n-1}T(i)+cn$$
使用替换法证明 $T(n)=O(n3^{n-1})$。
$T(1)=1\le c$，对 $n\ge 2$有：
$$\begin{align} T(n) &\le 2\sum_{i=1}^{n-1}T(i)+cn\\ &\le 2\sum_{i=1}^{n-1}ci3^{i-1}+cn\\ &\le c·(2\sum_{i=1}^{n-1}i3^{i-1}+n)\\ &= c·(2·(\frac{n3^{n-1}}{3-1}+\frac{1-3^n}{(3-1)^2})+n)\\ &=cn3^{n-1}+c·(\frac{1-3^n}{2}+n)\\ &=cn3^{n-1}+\frac{c}{2}(2n+1-3^n)\\ &\le cn3^{n-1} \end{align}$$
所以 RECURSIVE-MATRIX-CHAIN更高效。
注释： $$f(x)=\sum_{i=1}^{n-1}x^i,对f(x)求导得到：\sum_{i=1}^{n-1}ix^{i-1}=\frac{nx^{n-1}}{x-1}+\frac{1-x^n}{(x-1)^2}$$

15.3-2
递归树略，无效的原因是没有重叠子问题。

15.3-3
具有最优子结构性质。假设 $A_{ij}$是最优解，一定存在一个 $k$使 $A_{ik},A_{k+1,j}$都是最大化。用剪切-粘贴方法可以证明。

15.3-4
举例为 $p_0=100,p_1=100,p_2=5,p_3=10,p_4=1$分别表示 $A_1,A_2,A_3,A_4$
按教授的意思选择 $k=2$有 $(A_1A_2)(A_3A_4)$，总共 $p_0·p_1·p_2+p_2·p_3·p_4+p_0·p_2·p_4=51000$
实际存在 $A_1((A_2A_3)A_4)$，总共 $p_0·p_1·p_4+p_1·p_2·p_3+p_1·p_2·p_4=15500$

15.3-5
给出一个长度为 4 的价格和限制表。

Length i	1	2	3	4
price Pi	15	20	33	36
limit li	2	1	1	1

若没有限制表，长度为 4 的切割方案是 4 个长度为 1 的总价是 60。
现在只能选择长度分别是 1,1,2 总价是 50 的切割方案，原因是在长度为 2 的子问题寻找最优解时不能继续切割成长度为 1,1 的方案。

15.3-6
首先假设在一次兑换中不能重复兑换某一种货币，比如兑换序列为 $i\rightarrow j\rightarrow i\rightarrow j...$。这个假设的原因是若 $r_{ij}>1/r_{ji}$，这样银行就要倒闭了。
当对任意 $k$都有 $c_k=0$时有最优子结构性质。假设从货币 $a$兑换到货币 $b$存在一个兑换序列 $k_1,k_2...k_m$，其中 $k_1=a,k_m=b$，使得 $r_{k_1k_2}r_{k_2k_3}...r_{k_{m-1}k_m}$最大。
利用剪切-粘贴方法证明，即假设最优兑换序列是 $k_i,k_{i+1}...k_j$，又存在另一个兑换序列 $k_i,k^{'}_{i+1}...k^{'}_{j-1},k_j$使得$r_{k_ik^{'}_{i+1}}r_{k^{'}_{i+1}k^{'}_{i+2}}...r_{k^{'}_{j-1}k_j}>r_{k_ik_{i+1}}r_{k_{i+1}k_{i+2}}...r_{k_{j-1}k_j}$，我们用$k_i,k^{'}_{i+1}...k^{'}_{j-1},k_j$序列代替 $k_i,k_{i+1}...k_j$得到更优解。
当 $c_k$为任意值时，此时不一定具有最优子结构，举个例子，从货币 1 兑换到 货币 4，汇率分别是 $r_{12}=2,r_{13}=2.5,r_{14}=6,r_{23}=1.5,r_{24}=3,r_{34}=3$，其中 $r_{ii}=1,r_{ji}=1/r_{ij}$。令 $c_1=2,c_2=c_3=3$。所以兑换货币 1 到货币 4 有 5 种兑换方法，最优解是序列 $1,2,3,4$，最后 1 个单位的货币 1 兑换成 6 个单位的货币 4。
然后检查子结构，从货币 1 兑换到货币 3，最优兑换序列就是 $1,3$。这个兑换序列并不是 $1,2,3$。