什么是动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

斐波那契数列简介

由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。例如1、1、2、3、5、8、13、21。

递进求解

朴素解法（递归）

func fib(n int) int{
   if n == 1 || n == 2{
      return 1
   }
   return fib(n-1)+fib(n-2)
}

上述基本解法就是采用递归的方式，其时间复杂度为O(2^N)，可以用下面画的图方便理解运行过程。

记录子问题结果求解

// memo 为全局变量

func fib_memo(n int) int{
   var result int
   if result,ok := memo[n];ok {
      return result
   }
   if n == 1 || n == 2{
      result =  1
   }else{
      result = fib_memo(n-1)+fib_memo(n-2) // 2n次调用
   }
   memo[n] = result
   return result
}

上述代码修改保存了子问题中的结果，这样的话，下次取结果直接从保存好的map中去除对应的结果已减少运算，这样的话算法的复杂度减少到O(n)，准确的来说是O(2n+1)，运行示例图如下图所示。

自下而上的解法（非递归解法）

func fib_bottom_up(n int)int{
   if n == 1 || n == 2 {
      return 1
   }
   memo := make(map[int]int)
   memo[1] = 1
   memo[2] = 1
   for i := 3;i <= n;i++ {
      memo[i] = memo[i-1]+memo[i-2]
   }
   return memo[n]
}

上述解法是从自下而上的，整个的复杂度为O(n)，也减少了递归中的栈调用。

总结

分析下来可以发现动态规划存在几个特征；如下：

• 同一层次：即由同一个大问题拆分得到的多个小问题；

• 互相独立：排序如[2,1,4,3,6,5]拆分为A：[2,1,4]和B：[3,6,5]，子问题A和B的排序互不影响，各排各的；

• 结果传递：如0-1背包，容量C里判断放入(a,b,c,d,e)中的哪些，拆成两部分(a)和(b,c,d,e)，拿第二部分来看，选择放入谁必须先知道第一部分(a)是否放入了，因为它的结果直接影响背包所剩容量。