基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有 的解。动态规划算法与 类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从 问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

 

基本概念

　　1. 多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。

各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.

　　2．动态规划问题中的术语

：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。

 

用个示例引入一下：

斐波那契（多阶段决策问题）

 

def fibnacci(n):     if n ==1 or n ==2:         return 1     else:         return fibnacci(n-1)+fibnacci(n-2) # print(fibnacci(11)) 斐波那契（动态规划（DP）思想 = 递推式 + 重复子问题）

def fibnacci_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(fibnacci_no_recurision(100))

 

 

 

p = [0,1,5,8,9,10,17,17,20,24,30] def cut_rod_recurision_1(p,n):  #复杂度o(2n*n)     if n == 0 :         return 0     else:         res = p[n]         for i in range(1,n):             res = max(res,cut_rod_recurision_1(p,i) + cut_rod_recurision_1(p,n-i))             #   现有方式的价值  和从第一次到最后一次+剩余次数的最大值         return res 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 def cut_rod_dp(p,n):         #复杂度o(n*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] def cut_rod_extend(p,n):     r = [0]     s = [0]     for i in range(1,n+1):      #左边是1 于range(1,n+1)比较，如果大于上一次保存的列表人r和s         res_r = 0   #价格最大值         res_s = 0   #价格最大值对应方案左边不切割部分长度         for j in range(1,i+1):  #j=1             if p[j]+r[i-j] > res_r :                 res_r = p[j] + r[i-j]                 res_s = j         r.append(res_r)         s.append(res_s)     return r[n],s def cut_rod_solution(p,n):     r,s = cut_rod_extend(p,n)  #左边不切割最优长度，迭代右边剩下长度最优方案     ans = []     while n > 0 :         ans.append(s[n])         n-=s[n]     return ans