題目描述
一只青蛙一次可以跳上 1 級(jí)臺(tái)階,也可以跳上 2 級(jí)臺(tái)階粹胯。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法.答案需要取模 1e9+7(1000000007),如計(jì)算初始結(jié)果為:1000000008,請(qǐng)返回 1
題目描述
- 重復(fù)子問(wèn)題
- 答案取模
參數(shù)說(shuō)明
/**
* @param {number} n
* @return {number}
*/
題解及實(shí)現(xiàn)
1. 遞歸
題目滿足如下等式,故可以遞歸計(jì)算
f(n) = f(n-1)+f(n-2); n>2
f(n) = 2; n=2;
f(n) = 1; 0<=n<=1
var numWays = function (n) {
if (n <= 1) return 1;
if (n === 2) return 2;
return (numWays(n - 1) + numWays(n - 2)) % 1000000007;
};
時(shí)間復(fù)雜度:O(2^n)
- 資源使用情況
超出時(shí)間限制
2. 動(dòng)態(tài)規(guī)劃之自頂而下的備忘錄法
因?yàn)樯婕暗街貜?fù)子問(wèn)題的遞歸計(jì)算很耗費(fèi)時(shí)間,所以新建一個(gè)數(shù)組用于保存計(jì)算過(guò)的遞歸式的值,下次再遇到的時(shí)候直接查詢值而不是遞歸計(jì)算
var numWays = function (n) {
let cache = new Array(n + 1).fill(-1); ///備忘錄
count(n, cache); // 填充備忘錄
return cache[n];
};
function count(n, cache) {
if (n <= 1) cache[n] = 1;
if (n === 2) cache[n] = 2;
if (cache[n] !== -1) return cache[n];
else cache[n] = (count(n - 1, cache) + count(n - 2, cache)) % 1000000007;
return cache[n];
}
時(shí)間復(fù)雜度:O(n),每新增一項(xiàng)直接在備忘錄取值就行,相當(dāng)于填充備忘錄的時(shí)間
- 資源使用情況
- 執(zhí)行用時(shí)：80 ms, 在所有 JavaScript 提交中擊敗了 72.48%的用戶
- 內(nèi)存消耗：37.6 MB, 在所有 JavaScript 提交中擊敗了 6.45%的用戶
問(wèn)題:再遞歸樹(shù)的一邊計(jì)算的時(shí)候,還是要遞歸
3. 動(dòng)態(tài)規(guī)劃之自底向上由子得父法
同樣創(chuàng)建一個(gè)備忘錄數(shù)組,不過(guò)此次填充的順序是由小到大填充,略過(guò)遞歸計(jì)算填充帶來(lái)的性能消耗
var numWays = function (n) {
let cache = new Array(n + 1).fill(-1);
cache[0] = cache[1] = 1;
cache[2] = 2;
for (let i = 3; i <= n; i++) {
cache[i] = (cache[i - 1] + cache[i - 2]) % 1000000007;
}
return cache[n];
};
時(shí)間復(fù)雜度:O(n),計(jì)算備忘錄的值的時(shí)間
- 資源使用情況
- 執(zhí)行用時(shí)：76 ms, 在所有 JavaScript 提交中擊敗了 84.80%的用戶
- 內(nèi)存消耗：37.6 MB, 在所有 JavaScript 提交中擊敗了 5.46%的用戶
問(wèn)題:典型空間換時(shí)間
4. 動(dòng)態(tài)規(guī)劃之自底向上臨時(shí)數(shù)保存法
可以想到,由于自底向上法每往后計(jì)算一個(gè)數(shù)只會(huì)用到前面兩個(gè)數(shù)的值再相加,所以不用數(shù)組保存,直接換成臨時(shí)數(shù)保存
var numWays = function (n) {
if (!n || n === 1) return 1;
let a = 1; //臨時(shí)保存n-2的值
let b = 2; //臨時(shí)保存n-1的值
let result = n === 2 ? 2 : 0;
for (let i = 3; i <= n; i++) {
result = (a + b) % 1000000007;
a = b;
b = result;
}
return result;
};
時(shí)間復(fù)雜度:O(n)
- 資源使用情況
- 執(zhí)行用時(shí)：80 ms, 在所有 JavaScript 提交中擊敗了 72.48%的用戶
- 內(nèi)存消耗：37.7 MB, 在所有 JavaScript 提交中擊敗了 5.00%的用戶
空間復(fù)雜度:O(1)
