算法之走楼梯问题

Question

A 上楼梯时，B 从同一楼梯往下走。每次不一定只走 1 级，最多可以一次跳过 3 级（即直接前进 4 级）。
但无论走多少级，1 次移动所需时间不变。两人同时开始走，求共有多少种“两人最终同时停在同一级”的情况（假设楼梯宽度足够，可以相互错开，不会撞上。另外，同时到达同一级时视为结束）。

举个例子，有 4 级楼梯的时候，结果共有 4 种情况.

下面是我仿照作者例子中给的代码写的js版本。

//走楼梯问题，递归方法求解.

//来写一个复制Number类型的函数
function NumCopy(num) {
    var copy = num-0;
    return copy;
}

let N = 4, steps = 3, memo = {};
function move(a, b) {
    if([a, b] in memo) {
        return memo[[a, b]];
    }
    if(a>b) {
        return memo[[a, b]] = 0;
    }
    if(a == b) {
        return memo[[a, b]] = 1;
    }
    if(b>a) {
        for(let i=1; i<=steps; i++) {
            for(let j=1; j<=steps; j++) {
                cnt += move(NumCopy(a+i), NumCopy(b-j));
            }
        }
    }
    memo[[a, b]] = cnt;
}
let cnt = 0;
console.log(move(0, N));

这次又不知道哪错了？

Answer 1

递归时尤其要注意 终止条件 和 条件分支的返回，没有深读你的代码，我觉得应该是缺少了一个return

Answer 2

let N = 10, steps = 4, memo = {};
function move(a, b) {
    if(a>b) {
        return memo[[a, b]] = 0;
    }
    if(a == b) {
        return memo[[a, b]] = 1;
    }
    let cnt = 0;
    for(let i=1; i<=steps; i++) {
        for(let j=1; j<=steps; j++) {
            cnt += move(a+i, b-j);
        }
    }
    memo[[a, b]] = cnt;
    return memo[[a, b]];
}
console.log(move(0, N));

有两个地方写错了，第一处是let cnt = 0应写在函数内，之后，要想输出结果，应该给函数加个返回值。