动态规划核心思想：记住已经解决过的子问题的解。
动态规划的两种形式
- 自顶向下的备忘录
- 自底向上
实例
Fibonnacci
使用动态规划思想实现斐波拉契数列Fibonacci
"""
使用动态规划思想实现斐波拉契数列
"""
def fibonacci(n):
if n <= 0:
return n
memo = [-1] * n
return fib(n, memo)
def fib(n, memo):
if memo[n - 1] != -1:
return memo[n - 1]
if n <= 2:
memo[n - 1] = 1
else:
memo[n - 1] = fib(n - 2, memo) + fib(n - 1, memo)
return memo[n - 1]钢条切割问题
Serling公司购买长钢条，将其切割为短钢条出售。切割工序本身没有成本支出。公司管理层希望知道最佳的切割方案。假定我们知道Serling公司出售一段长为i英寸的钢条的价格为pi(i=1,2,…，单位为美元)。钢条的长度均为整英寸。图15-1给出了一个价格表的样例。
钢条切割问题是这样的：给定一段长度为n英寸的钢条和一个价格表pi(i=1,2,…n)，求切割钢条方案，使得销售收益rn最大。注意，如果长度为n英寸的钢条的价格pn足够大，最优解可能就是完全不需要切割。