一周算法分享

算法简述

LeetCode - 70 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

解决思路

通常对普通算法问题的解决思路常用的办法是分拆问题。一个大问题能够分拆为若干个小问题，然后对小问题进行递归或者局部解决。

n阶爬楼梯问题适合用这种思路，但首先需要找到分拆的规律。

从特殊情况推算普遍规律

一眼看上去没法直接看出普遍规律，那么可以先用特殊情况先归纳一遍，然后再反推普通规律。

首先取几个值，

n = {1, 2, 3, 4}

对于简单的情况可以直接计算出结果，设 k 为需要的步数，steps 是实际爬楼梯的方案集合

n = 1, k = 1, steps = {1} n = 2, k = 2, steps = { {1, 1}, {2}} n = 3, k = 3, steps = { {1, 1, 1}, {2, 1,}, {1, 2}} n = 4, k = 5, steps = { {1, 1, 1, 1}, {2, 1, 1}, {1, 2, 1}, {1, 1, 2}, {2, 2}}

接下来分析特殊情况的4个例子可以找到简单的规律

k[4] = k[3] + k[2] = 3 + 2 = 5

那么从这里是否可以推断得到下面的普遍规律呢？

k[n] = k[n - 1] + k[n -2]

我们需要一个严谨的推断过程。这里可以考虑动态规划的思路，首先分拆问题，当阶数为i时，设置k = x

1. n = i, k = x
2. n = i + 1, k = y 首先必然可以得到的其中一个i + 1阶的方案是在原先i阶的方案上再走1步得到。反过来说，当n= i + 1时，对于所有最后一步是1步的方案，steps 和 n = i 时是相等的。

那么最后一步是2步的方案是怎样的呢？也是同样的思路可以得到， n = i + 1时，最后一步是2步的所有方案，steps 和 n = i - 1时是相等的，而且绝对不会和n = i时重叠。所以可以得到结论是 3 n = i + 2, k = x + y

也就是说，

steps[n] = steps[n -1] + steps[n - 2]

算法实现

基于上面的推论，这个算法可以用两个思路实现。一个是从下往上计算n = i时的方案数， 另一个是从上往下用递归计算n = i时的方案数。

方案一

最简单的思路是用数组实现，定义数组 steps[n]，n = i，然后从0开始到 i - 1逐个计算方案数。很容易看出这个方案的缺点是内存空间占据太多，当n很大的时候分配的空间会很浪费。

注意观察上面的推论，实际上我们只需要用两个int即可以记录步数的变化，

steps[n] = steps[n -1] + steps[n - 2]

比如定义steps[2]，用[0]记录 n - 1 的方案数，[1] 记录n - 2的方案数，然后不断相加并且交换两个数的位置，这样也可以得到 n = i 时的方案数。下面是具体代码实现

public static int ways(int steps) {
   int[] ways = new int[2];
   ways[0] = 1;
   ways[1] = 2;
   int k = 1;
   while(k < steps) {
      ways[(k-1) % 2] += ways[k % 2];
      k++;
   }
   return ways[(k - 1) % 2];
}

方案二

递归的思路非常简单，只要把我们的推论翻译进去就行，代码

public static int waysRecursive(int n) {
   if (n > 2) {
      return waysRecursive(n - 1) + waysRecursive(n - 2);
   } else {
      if (n == 2) {
         return 2;
      } else if (n == 1) {
         return 1;
      }
   }
   return 1;
}

算法评估

这两个算法都可以正确计算出结果，但是在时间开销上差异很大。方案二在n大于43之后就会运算超过2秒，而方案一在同样的n值下只需要1ms就可以得到结果。

因为方案二的递归实际上是个指数爆炸的算法，算法复杂度是 O(n²)， 也就是每一个n的方案都会被重复计算接近于无数次。

因此对于这个问题的最优解是方案一。

但在LeetCode上方案一并没有取得最好的结果， 内存和算法时间开销都只在中位数，应该还可以再优化到更好的水平。