第15章——动态规划（上1）

Dynamic PROGRAMMING

问题引入 —— 钢条切割问题

Given a rod of length n inches and a table of prices pi for i = 1,2,3,…,n, determine the maximum revenue r(n) obtainable by cutting up the rod and selling the pieces.

问题分析

In the best solution, we cut i inch from rod at the first time, r(n)= p(i) + r(n-i)，
r (n-i) is totally the same problem with just smaller size.
&
The n-i part of best solution must be the best solution for problem n-i; Why r(n-i)must be the best solution for problem n-i ? ——可用反证法求证

Recursive top-down implementation

伪代码如下：

Recursive top-down implementation – good ?

Dynamic Programming – top down memoization——动态规划-自顶向下记忆

Avoid resolving same sub-problem

伪代码如下：

课堂练习
In class exercise:
compute r[1] – r[10]with bottom up method

以下仅代表个人的答案：

建议的读者，跟着代码计算，便于深入体会它的意义。

Dynamic Programming – Efficiency

$\theta$θ($n^2$n2)

最终代码为：

这里 S 记录了 切割的方式 r 记录了，钢条长度为 i 时的切割的最大盈利