走楼梯问题

问题：有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。一共有多少种走法。（和铺瓷砖问题是一样的）

暴力枚举很简单，先选择可能性，再根据排列组合公式，记录。
但是显然阶乘是可能溢出的，且其时间复杂度为O(n^2)（这里加上了求阶乘的复杂度）

  1. int N = 10;
  2.     int M[2] = {1,2};
  3.     int sum = 0;
  4.     for (int i = 0; i <= 10/M[0]; ++i)
  5.     {
  6.  if ((N - i*M[0]) % M[1] != 0) continue;
  7.  int n = (N - i*M[0]) / M[1] + i;
  8.  // 这里是伪代码,!表示阶乘
  9.  sum += n!/ (i!*(N - i)!)
  10.     }

能不能把问题简单化呢？假设对台阶为10的求解是F(10)，那么F(10)的最后一步是不是只能是停留在第8阶或者第9阶呢？

那么这个F(10)是不是相当于F(9)+F(8)，注意不要理解错了，这里指的是最后一步，如果F(8)的时候你选择走一步，那么这个问题应该归类于F(9)

那么我们递推会发现,这是一个数学问题

  1.    F(n)=F(n-1)+F(n-2)
  2.    F(10)=F(9)+F(8)
  3.    F(9)=F(8)+F(7)
  4.    F(8)=F(7)+F(6)
  5.    ...
  6.    F(2)=F(1)+F(0)  F(2)=2
  7.    F(1)=F(0)       F(1)=1
  8.    F(0)=1


求F(n),显然这是一个栈底已知的递归算法，那么我们自下而上的看,只需一个简单的循环求和就行了

  2. int Fi_1=0 ,Fi_2=0;
  3. for (int i=1;i<=n;i++)
  4. {
  5.    if(i=1) Fi_2=1;
  6.    if(i=2) Fi_1=2;
  7.    int Fi=Fi_1+Fi_2;
  8.    Fi_2 = Fi_1;
  9.    Fi_1 = Fi;
  10. }
  11. return Fi_1


思路写出来后，小小的优化一下，能手动算的，咱自个儿算算

  1. unsigned long long F(int n)
  2. {
  3.     if (n < 0)
  4.  return 0;
  5.     if (n == 0)
  6.  return 1;
  7.     if (0 < n && n <= 3)
  8.  return n;
  9.     unsigned long long Fi_1 = 3;
  10.     unsigned long long Fi_2 = 2;
  11.     unsigned long long Fi = 0;
  12.     for (int i = 4; i <= n; ++i)
  13.     {
  14.          Fi = Fi_1 + Fi_2;
  15.         Fi_2 = Fi_1;
  16.         Fi_1 = Fi;
  17.     }
  18.     return Fi;
  19. }

这个算法的时间复杂度变成O(n),当然溢出问题还是没有解决，暂时只能通过限制输入

如果每一步能跨出m种可能，显然暴力算法时间复杂度在选择可能性这一步就爆炸了，指数级算法是不可取的。那么这个动态规划算法仅需增加m-2个变量即可完美胜任。

那么回过来想

动态规划是什么

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，解决这类过程优化问题的方法，也就是推导出上面F(n)=F(n-1)+F(n-2)的思路。

点击关注，持续推送质量好文；如有不当，欢迎指出；转载请注明出处。