适用动态编程的两个条件

1。最优子结构
2。重叠子问题
昨天马云说，最简单的事情最难做好。我想把最简单的事情做好先。

证明-矩阵最小乘数问题

show that the solution to the recurrence is Ω(2ⁿ).
这个问题是这样的：
Ω(2ⁿ) 即只要 >= 2^{n
第一步，n=1，有p(1) = 1 =} 2⁰
第二步，n <>Ω(2ⁿ) >= 2ⁿ
第三步，n= l ，p(n) = sigma: p(k)p(n - k)。因为k & n-k 小于l，于是有
p(n) >= 2^k * 2^n-k= 2<sup>n

符号所代表的意义相当的重要，没有</sup>Ω(2ⁿ)>=2^{n的解释，基本很难证明这个命题。}

今天最后一个

There might exist some e_i, a_i,j, and t_i,j values for which FASTEST-WAY produces l_i[j] values such that l₁[j] = 2 and l₂[j] = 1 for some station number j. Assuming that all transfer costs t_i,j are nonnegative.

证明：
l₁[j] = 2 说明 f1[j] = f2[j-1] + a1[j] + t2[j-1] 说明 f2[j-1] + a1[j] + t2[j-1] < f1[j-1] + a1[j]，说明f2[j-1] + t2[j-1] < f1[j-1] ，(1)
l₂[j] = 1 说明 f2[j] = f1[j-1] + a2[j] + t1[j-1] 说明 f1[j-1] + a2[j] + t1[j-1] < f2[j-1] + a2[j]，说明
f1[j-1] + t1[j-1] < f2[j-1]， (2)
(1) + (2) 得到：t2[j-1] + t1[j-1] < 0
但是t_i,j are nonnegative，所以产生了矛盾．命题错误．

这个命题说明了什么？为什么反过来不正确呢？难道不应该是对称的吗？
以上是纯形式化的证明，由于没有用我的实际经验进行验证，所以让我觉得心中没有底．

再请证明

∑²_i=1∑ⁿ_j=1 r_i(j) is exactly 2ⁿ⁺¹ - 2

证明如下：
∑²_i=1∑ⁿ_j=1 r_i(j) = ∑²_i=1∑ⁿ_j=1 2^n-j = ∑²_i=1(2⁰ + ... + 2^n-1_{) = (}2¹ + ... + 2ⁿ) = 2ⁿ⁺¹ - 2

请证明

r1(n) = r2(n) = 1

r1(j) = r2(j) = r1(j+1) + r2(j+1)

Use above equations to show that r_i(j), the number of references made to f_i[j] in a recursive algorithm, equals 2^{n - j}.

证明如下：

第一步：n - j = 1
r1(j)=r2(j) = r1(j+1) + r2(j+1) = r1(n) + r2(n) = 2 = 2<sup>n - j

第二步：若n - j = k</sup>
r1(j)=r2(j) = r1(j+1) + r2(j+1) = 2^{n - j}

若当n - j = k + 1
r1(j) = r1(j+1) + r2(j+1)
因为 n - (j+1) = k，所以 r1(j) = 2^{n - (j +1)} + 2^{n - (j +1)} = 2<sup>n - j

综上，命题得证。
纪念，走出数学系后的第五个年头的一个归纳法证明。</sup>

Dynamic programming - Pattern to find optimal substructure

1. Solution to the problem consists of making a choice.
2. Suppose for a given problem, a choice is given to lead to an optimal solution.
3. Given this choice, determine which subproblems ensue and how to best characterize the resulting space of subproblems.
4. Show solution to subproblem must be optimal by using "cut-and-paste" technique.