动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
使用动态规划特征：
- 求一个问题的最优解
- 大问题可以分解为子问题，子问题还有重叠的更小的子问题
- 整体问题最优解取决于子问题的最优解（状态转移方程）
- 从上往下分析问题，从下往上解决问题
- 讨论底层的边界问题
动态规划最重要的有三个概念：1、最优子结构 2、边界 3、状态转移方程
有十个台阶，从上往下走，一次只能走一个或两个台阶，请问总共有多少种走法？
1、最优子结构：我们来考虑要走到第十个台阶的最后一步，最后一步必须走到第八或者第九。不难得到 f(10) = f(9)+f(8)。f(9) = f(8)+f(7)
2、边界：f(1) = 1, f(2) = 2
3、状态转移：f(n) = f(n-1) + f(n-2)
解法1：递归：
哟，写bug呢？？
动态规划算法python实现
一、什么是动态规划
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
使用动态规划特征：
1. 求一个问题的最优解
2. 大问题可以分解为子问题，子问题还有重叠的更小的子问题
3. 整体问题最优解取决于子问题的最优解（状态转移方程）
4. 从上往下分析问题，从下往上解决问题
5. 讨论底层的边界问题
动态规划最重要的有三个概念：1、最优子结构 2、边界 3、状态转移方程
二、走楼梯问题
有十个台阶，从上往下走，一次只能走一个或两个台阶，请问总共有多少种走法？
1、最优子结构：我们来考虑要走到第十个台阶的最后一步，最后一步必须走到第八或者第九。不难得到 f(10) = f(9)+f(8)。f(9) = f(8)+f(7)
2、边界：f(1) = 1, f(2) = 2
3、状态转移：f(n) = f(n-1) + f(n-2)
解法一、递归
def get_count(n):
if n == 1:return 1
if n == 2:return 2
else:
return get_count(n-1)+get_count(n-2)
print(get_count(10))解法二、备忘录算法
回顾一下上面的递归计算方法，我们不难看出，本来总共只有f(1)-f(N)个节点，硬生生被增加到2^N-1个，这就是产生了大量重复的运算。找到问题的根源，对应的解决方法就应运而生，那就是从下往上算，把以前计算过的数值，保存在一个哈希表中，然后后面计算时先查询一下，存在就无需计算。时间复杂度为O(n) ,空间复杂度为O(n)。但是在仔细一想其实，无需保存所有的f,每个f都只与前两个值相关，所以空间复杂度可以降低为O(1).我们来看看相关代码。
def get_count(n):
if n == 1:return 1
elif n == 2 :return 2
else:
l = [1,2]
for i in range(3,n):
l[0],l[1] = l[1],l[0]+l[1]
return l[0]+l[1]三、整数拆分
def func(n):
l = [1]
for i in range(3,n+1):
m = 0
for j in range(1,i//2+1):
m = max(m,j*(i-j),j*l[i-j-2])
l.append(m)
return l
print(func(10))四、最大子序和
def max_subarry(nums):
m = nums[0]
tem_m = nums[0]
pre = nums[0]
for i in range(1,len(nums)):
if pre<=0:
tem_m = nums[i]
pre = nums[i]
else:
pre+=nums[i]
tem_m+=nums[i]
if tem_m>m: m = tem_m
return m