文档介绍：有 8 万元的投资可以投给 3 个过目，每个项目在不同筒子数额下（以万元为单位）的利润如下表投资额
盈利
0
1
2
3
4
5
6
7
8
项目
项目 1
0
5
15hon
# coding:utf-8
def fib(number):
if number == 0 or number == 1:
return 1
else:
return fib(number - 1) + fib(number - 2)
欢迎下载 4
精品文库
if __name__ == '__main__':
print fib(35)
有一点开发经验的人就能看出， fib(number-1) 和 fib(number-2) 会导致我们产生大量的重复
计算，以上程序执行了 14s 才出结果，现在，我们把每次计算出来的结果保存下来，下一
次需要计算的时候直接取缓存，看看结果：
#!/usr/bin/env python
coding:utf-8 cache = {}
def fib(number):
if number in cache:
return cache[number]
if number == 0 or number == 1:
return 1
else:
cache[number] = fib(number - 1) + fib(number - 2)
return cache[number]
if __name__ == '__main__':
print fib(35)
耗费时间为 效果提升非常明显。
自底向上（ Bottom-Up ）
自底向上是另一种求解动态规划问题的方法， 它不使用递归式， 而是直接使用循环来计算所有可能的结果，往上层逐渐累加子问题的解。
我们在求解子问题的最优解的同时， 也相当于是在求解整个问题的最优解。 其中最难的部分是找到求解最终问题的递归关系式，或者说状态转移方程。
这里举一个 01 背包问题的例子：
你现在想买一大堆算法书，需要很多钱，所以你打算去抢一个商店，这个商店一共有 n 个
商品。问题在于，你只能最多拿 W kg 的东西。 wi 和 vi 分别表示第 i 个商品的重量和价值。
我们的目标就是在能拿的下的情况下， 获得最大价值， 求解哪些物品可以放进背包。 对于每
一个商品你有两个选择：拿或者不拿。
欢迎下载 5
精品文库
首先我们要做的就是要找到 “子问题 ”是什么，我们发现，每次背包新装进一个物品，就可以
把剩余的承重能力作为一个新的背包来求解，一直递推到承重为 0 的背包问题：
作为一个聪明的贼，你用 m[i,w] 表示偷到商品的总价值，其中 i 表示一共多少个商品， w 表
示总重量，所以求解 m[i,w] 就是我们的子问题，那么你看到某一个商品 i 的时候，如何决定
是不是要装进背包，有以下几点考虑：
该物品的重量大于背包的总重量，不考虑，换下一个商品；
该商品的重量小于背包的总重量，那么我们尝试把它装进去，如果装不下就把其他东西换出来，看看装进去后的总价值是不是更高了，否则还是按照之前的装法；
3. 极端情况，所有的物品都装不下或者背包的承重能力为 0，那么总价值都是 0；
由以上的分析，我们可以得出 m[i,w] 的状态转移方程为：
有了状态转移方程， 那么写起代码来就非常简单了， 首先看一下自顶向下的递归方式， 比较
容易理解：
#!/usr/bin/env python
coding:utf-8 cache = {} items = range(0,9)
weights = [10,1,5,9,10,7,3,12,5]
values = [10,20,30,15,40,6,9,12,18]
最大承重能力
W = 4
def m(i,w):
if str(i)+','+str(w) in cache:
return cache[str(i)+','+str(w)]
result = 0
特殊情况
if i == 0 or w == 0: