資訊專欄INFORMATION COLUMN
摘要：前言本系列總結(jié)了在前端面試中可能遇到的若干算法題，不定期更新最近看有同學(xué)面試遇到了階{{BANNED}}跳問題級臺階，每次最多允許跨步，求多少種跨越方式，下面是一個變種問題題目假設(shè)有級臺階，每次最多允許跨步，那么有多少種跨越方式思路采用自頂向下的思考方式
前言：本系列總結(jié)了在前端面試中可能遇到的若干算法題，不定期更新
最近看有同學(xué)面試遇到了n階{{BANNED}}跳問題（n級臺階，每次最多允許跨n步，求多少種跨越方式），下面是一個變種問題
題目：假設(shè)有n級臺階，每次最多允許跨m步（m<=n），那么有多少種跨越方式？ 思路：采用自頂向下的思考方式f(n,m) = f(n-1,m)+f(n-2,m)+...+f(n-m,m)
當(dāng)m=2時，這就是一個斐波那契數(shù)列。
同時，對于n階{{BANNED}}跳，即n=m時，用公式有以下特點(diǎn)：
f(n) = f(n-1)+f(n-2)+...+f(1);//①
f(n-1) = f(n-2)+f(n-3)+...+f(1);//②
①-② 即f(n) = 2f(n-1)，可以看出n階{{BANNED}}跳的結(jié)果，實(shí)際是一個等比數(shù)列，也就是f(n) = 2^(n-1)
function f(n,m) {
var count = 0;
if (n == 0) {
return 1;
}
if (n >= m) {
for (var i=1; i<=m; i++) {
count += f(n-i,m);
}
}else {
count += f(n,n);
}
return count;
}
解法2：非遞歸算法
