我是想记录一下这道题。
爬楼梯问题的递归解法
原题是这样的：
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
很容易想到这样的树状图结构：
利用递归算法进行实现应该是这样的：
class Solution {
private:
std::unordered_map<int,int> map;
public:
int climbStairs(int n)
{
// 递归终止条件
if(n==1) return 1;
if(n==2) return 2;
// 递归入口
return climbStairs(n-1) + climbStairs(n-2);
}
};
看似天衣无缝，然而…
其实仔细观察上述树状图，不难发现该算法的时间复杂度是 O ( 2 n ) O(2^n) O(2n)，每一层递归的复杂度是上一层的两倍，这样的效率可以说是糟糕的了。
有没有方法可以优化这样的递归？
记忆化递归
”记忆化递归“，这个算法有很多名字，比如“递归树的剪枝”，“备忘录递归”… 其核心思想就是去除递归过程中不必要的重复计算，以提高算法的效率。
那么我们要去除的”不必要的重复计算“在哪里呢，请看：
以同一数字展开的树状图当然是一样的，如果我们能够保存第一次计算时的结果，在以后遇到同样数字时直接使用先前计算得到的结果，就能给树状图”剪枝”，也就能消除“不必要的重复“了。
上述思路中，我们实际上需要储存的是树状图中的被展开数与其最终结果之间的关系，也就是键值对，那么哈希表就是最好的选择。
auto item = umap.find(n);
if(item != umap.end()) return item->second;
稍微写一个类似单元测试的框架，整体的代码是这样的：
#include <array>
#include <iostream>
#include <unordered_map>
class Solution {
private:
std::unordered_map<int, int> umap;
public:
int climbStairs(int n)
{
// 递归终止条件
if(n == 1) return 1;
if(n == 2) return 2;
// 时间优化，查询并尝试利用之前已经计算过的爬n个楼梯的方法数
auto item = umap.find(n);
if(item != umap.end()) return item->second;
// 递归入口，集成了时间优化的记录
auto buffer = climbStairs(n - 1) + climbStairs(n - 2);
// 时间优化，记录当前计算的爬楼梯数n与其方法数的对应关系到哈希表
umap.insert({ n, buffer });
return buffer;
}
};
Solution s;
bool test(int n, int target) { return s.climbStairs(n) == target; }
int main() noexcept
{
std::array<std::array<int, 2>, 7> tests{ 2, 2, 3, 3, 4, 5, 5, 8, 6, 13, 7, 21, 8, 34 };
for(auto& item : tests)
{
if(!test(item.at(0), item.at(1)))
{
std::cout << "failed on test(" << item.at(0) << "),it should be " << item.at(1) << ",but actually " << s.climbStairs(item.at(0)) << std::endl;
return -1;
}
}
std::cout << "PASSED\n";
return 0;
}
此时代码已经能够在力扣上通过，本地Linux上测试的结果表明，当n=45时，记忆化递归平均用时0.0016s，而原始递归平均耗时为4.618s，仅仅几行代码将效率提升了接近3000倍。
但是这样的提升也不是毫无代价的，为了实现记忆化，我们使用了一个哈希表，而哈希表恰好就是个拿空间换时间的主，难以避免的，记忆化递归也是在用空间换取时间。不过在大多数情况下，和节省的时间相比，多耗费的那点内存根本不值一提。
后记：本来想拓展到动态规划的，但是好像超出我目前的能力范围了，等我学会了再写吧。
参考资料
https://www.bilibili.com/video/BV1AB4y1w7eT