爬楼梯问题之二

       正如前文所说，我们把爬上N个台阶共有有多少种方法这一问题通过递归的方法得以了解决，但问题虽然解决了可我们想过这个程序的时空复杂度没有？

        首先，时间复杂度。它的时间复杂度是O(2^n)，随着楼梯台阶数的增长程序的运行时间呈指数增长。这是一种我们最不想看到的情况。再次，空间复杂度。由于采取函数的嵌套调用，程序运行所需空间也是相当大的。最后，那到底有没有更好的优化方法呢？

       答案是肯定的！如果大家把该问题从顶而下的展开来，应该能发现它的所有求解函数F(X),X€{N,N-1,...,1}展开式是以完全二叉树的形式组织起来的，且相邻节点的左右子树的值相同，这意味着在求解过程中存在重复的内容。

相同颜色的为重复的计算

        所以我们可以通过一个哈希表存储每一个求解函数的值，每当求解一个F(X)的时候先从哈希表中查看有无该函数值，如果有现成的值，则直接返回结果，如果没有就计算该值并把结果存入哈希表中。

图片发自简书App

        听着好复杂哦，那还有没有更简单的办法？答案也是肯定的！！！那就是☞自底向上。那么何为自底向上？如果仔细观察，我们会发现，F(3)的值只取决于F(1)和F(2)，F(4)的值只取决于F(3)和F(2)，...，F(N)的值只取决于F(N-1)和F(N-2)。好了有了这个结论，我们就可以"捡西瓜丢芝麻"了，而不是像哈希表一样，存储所有计算过的F(X)，这样是不是就大大大大减少了程序的空间复杂度？

图片发自简书App

更多精彩内容请关注☞leon_Geo