一周算法分享
一周算法分享
算法简述
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
- n = i, k = x
- 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上方案一并没有取得最好的结果， 内存和算法时间开销都只在中位数，应该还可以再优化到更好的水平。