Skip to content
Branch: master
Find file History

Latest commit

Fetching latest commit…
Cannot retrieve the latest commit at this time.

Files

Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
README.md
dynamic.js
node.js
recursive.js

README.md

爬楼梯

解法1 递归

假设有n阶楼梯 P1:前一次爬为则可以为 2 或者 1 步,那么剩余的阶梯数量则为 n-1 或 n-2 个 P2: n-1和n-2也分别可以的前一次爬 也可以为 2 或者 1 步

所以可以看出,f(n) = f(n-1) + f(n-2),则递归到阶梯只剩下 1 或者 2 步 但计算到45阶梯的时候,已经接近需要8秒。 这种方法的时间复杂度为O(2^n)

解法2 保存节点

实际上由上面可以看出来,这个算法其实是一个一个的分支,即一个二叉树,有多少种解开方法,就是有多少个节点。 那么必然有节点是重复的,比如说,f(n) = f(n-1) + f(n-2) f(n-1) = f(n-2) + f(n-3) 那实际上,f(n-1)就是重复的节点,由此可以得出算法二: 递归的同时,保存计算过的节点。 这种方法的时间复杂度也为O(2^n)

解法3 动态规划

f(3) = f(2) + f(1) f(4) = f(3) + f(2) f(5) = f(4) + f(3)

那么可以看出,每一个阶梯,只与前两个阶梯有关,所以我们只保存前两次的数据。

You can’t perform that action at this time.