算法之走楼梯问题

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

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

Answer 2

let N = 10, steps = 4, memo = {};function move(a, b) {&nbsp; &nbsp; if(a>b) {&nbsp; &nbsp; &nbsp; &nbsp; return memo[[a, b]] = 0;&nbsp; &nbsp; }&nbsp; &nbsp; if(a == b) {&nbsp; &nbsp; &nbsp; &nbsp; return memo[[a, b]] = 1;&nbsp; &nbsp; }&nbsp; &nbsp; let cnt = 0;&nbsp; &nbsp; for(let i=1; i<=steps; i++) {&nbsp; &nbsp; &nbsp; &nbsp; for(let j=1; j<=steps; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cnt += move(a+i, b-j);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; memo[[a, b]] = cnt;&nbsp; &nbsp; return memo[[a, b]];}console.log(move(0, N));有两个地方写错了，第一处是let cnt = 0应写在函数内，之后，要想输出结果，应该给函数加个返回值。