动态规划示什么意思？先列一个题目出来：

爬楼梯问题

爬楼梯的时候，可以一次跨一个台阶，也可以一次跨两个台阶；那么要到达第n个台阶，有多少种上楼的方法？

分析

这道题目，是一个典型的动态规划问题，假设现在n=5；要到达第5个台阶，只存在两种情况：

  1. 在台阶4，跨1个台阶；
  2. 在台阶3，跨两个台阶；

现在问题发生了变化，从到达5阶，分裂成了两种情况，到达5阶的上楼方法=到达4阶的方法+到达3阶的方法；那么，对这两种情况继续进行分解：

  1. 到达3阶的方法，存在两种，到达1阶，然后跨越两个台阶；或者到2阶，跨越1阶；
  2. 到达4阶的方法，存在两种，到达2阶，然后跨越2个台阶；或者到达3阶，跨越1个台阶；

在上述两个问题中，到达5阶的方法，最终被分解为，到达3阶，和到达4阶的方法的总和；
如果此时按照穷举法：

  1. 到达3阶，存在3中方法(1,1,1)(1,2)(2,1)
  2. 到达4阶，存在5中方法(1,1,1,1)(2,1,1)(1,2,1)(1,1,2)(2,2)

很明显，想要到达5阶，存在8中方法；

穷举法的劣势

当5阶台阶的时候，当然还可以使用穷举，因为情况不是很复杂，我们仍旧可以通过穷举获取到到达3阶和到达4阶的各种情况；但是当n更大的时候呢？？
这个时候就不能再继续穷举了，计算过程会很复杂；

使用递归的思想

既然5阶可以分裂为到达4阶和到达3阶的方式的和；
那么不用穷举：

  1. 到达3阶也可以分裂为到达1阶和到达2阶的方式的和；
  2. 到达4阶也可以分裂为到达2阶和到达3阶的和；而到达3阶的方法在步骤1中就计算过；

计算

  1. 到达3阶=到达1+到达2；到达1阶很明显只有1中方法，到达2则有两种方法；所以到达3就有三种方法（1+2）
  2. 到达4阶=到达2+到达3=到达1+（到达1+到大2）；到达4的方法有5种(2+1+2)；
  3. 到达5阶=到达3+到达4；共有8种方法；

如果你仔细观察的话，会发现..这实际上是一个斐波那契数列，这正好是一个巧合…这个题目是一个尾递归的问题，所以可以被优化成循环解决…但是我们还是使用递归的思想去写一下代码

递归代码

  1. int mehtods(int order)
  2. {
  3.     if(order ==1 )
  4.         return 1;
  5.     if(order ==2)
  6.         return 2;
  7.     return methods(order-1)+methods(order-2)
  8. }

这样，order会被逐层分解到最终是1阶或者2阶；
但是这个代码还是存在问题的…在上一个分析种，可以看到，5被分解为3和4，4又会被分解为2和3，如果按照上面的代码来实现的话..到达3阶的方式被计算了2次，在4的分支中计算了一次，在3的分支中又要被计算一次，这样会造成资源的浪费，在n=5的时候这种浪费不是很明显，但是当n变大的时候，这种重复计算将会变得很多很多
优化一下:

  1. int[] array = new array[楼梯总阶数];
  2. array[1]=1;
  3. array[2]=2;
  4. int methods(int order)
  5. {
  6.     if(order ==1 )
  7.     {
  8.         return array[1];
  9.     }
  10.     if(order ==2 )
  11.     {
  12.         return array[2];
  13.     }
  14.     int result;
  15.     if(array[order-1]!=null && array[order-2]!=null)
  16.         result = array[order-1]+array[order-2];
  17.     else if(array[order-1] != null && array[order-2] ==null)
  18.     {
  19.         result = array[order-1] + methods(order-2)
  20.     }
  21.     else if(array[order-1] ==null && array[order-2] !=null)
  22.     {
  23.         result = array[order-2] +methods(order-1);
  24.     }
  25.     else
  26.     {
  27.         result = methods(order-1)+method(order-2);
  28.     }
  29.     array[order] = result;
  30.     return array[order];
  31. }

还用5来举例，首先array种只有1和2的内容，5分裂成3和4，目前在array种都是null；执行methods(3)和methods(4)；
methods(3)执行，将3分裂成1和2，执行methods(1)和methods(2)，返回1和2；在methods(3)种，result=3，并且将array[3]的数值填上；
methods(4)执行，将分类成3和2，此时array[3]中已有内容，直接拿来用就可以，array[2]中也有内容，直接拿来用；
这样就解放了一次对阶数=3的计算；算好的就存起来，下次直接用；