算法之走楼梯问题

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应写在函数内，之后，要想输出结果，应该给函数加个返回值。