动态规划——DP 核心：递推式

动态规划(DP)的思想： 最优子结构 = 调试；重复子问题

从斐波那契数列看动态规划： 斐波那契数列：Fn = Fn-1 + Fn-2 使用递归和非递归的方法来求解斐波那契数列的第n项 使用递归写法：

def fibnacci(n):
    if n==1 or n==2:
        return 1
    else:
        return  fibnacci(n-1) + fibnacci(n-2)
print(fibnacci(100))

递归很慢！！！

使用非递归写法：

def fibnacii_no_recurision(n):
    f = [0,1,1]
    if n > 2:
        for i in  range(n-2):
            num = f[-1] + f[-2]
            f.append(num)
    return  f[n]
print(fibnacii_no_recurision(100))

当n等于100时，可以看出非递归计算得很快，但是递归很慢，这就涉及到子问题的重复问题了

这里可以看出递归的时候，每个f(n) 都是独立的，所以一直重复计算一个一样的值，使得效率低下，

非递归的想法就是动态规划的思想

动态规划之钢条切割问题

假定我们知道某公司出售一段长度为i英寸的钢条的价格为p钢条长度为整英寸如图给出价格表的描述（任意长度的钢条价格都有） 现在先给一段长度为n的钢条，问怎么切割，获得的收益最大 rn? 考虑n=4的时候，有以下8种切割方式 假如一个最优解把n段切成了k段（1<=k<=n）,那么最优切割方案： i及下标表示第i段的长度，n为钢条的总长度。

最大收益： p及下标表示第i段的收益，r为钢条的总收益

设长度为n的钢条切割后最优收益值为rn，可以得出递推式： rn = max（pn，r1+rn-1,r2+rn-2…） 第一个参数pn表示不切割 其他n-1个参数分别表示另外n-1种不同切割方案，对方案i=1，i=2… 将钢条切割为长度i和n-i两段 方案i的收益为切割两段的最优收益之和 小问题的最优解可以构造大问题的最优解的时候就称为最优子结构 钢条切割问题还存在更简单的递归求解方案 从钢条的左边切割下长度为i的一段，只对右边剩下的一段继续切割左边的不再切割 递推式简化为：rn = max(pi+rn-i) 这里的pi帮大家理解下：始终还要切 一直切到r1 递归代码如下

#这里是公式为：rn = max（pn，r1+rn-1,r2+rn-2........）
def cut_rod_recurision(p,n):
    if  n==0:
        return 0
    else:
        res = p[n]
        for i in range(1,n):
            res = max(res,cut_rod_recurision(p,i)+cut_rod_recurision(p,n-i))
        return res

print(cut_rod_recurision(p,9))

#这里是公式为：rn = max(pi+rn-i)
def cut_rod_recurision_2(p,n):
    if  n==0:
        return 0
    else:
        res = 0
        for i in range(1,n+1):#切
            res = max(res,p[i] + cut_rod_recurision_2(p,n-i))
        return res

print(cut_rod_recurision_2(p,9))

dp解法如下：

def cut_road_dp(p,n):
    r = [0]
    for i in range(1,n+1):
        res = 0
        for j  in  range(1,i+1):
            res = max(res,p[j] + r[i-j])
        r.append(res)
    return r[n]
#用空间换时间