在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

鍍金池/ 問答/HTML/ 算法之走樓梯問題

算法之走樓梯問題

A 上樓梯時，B 從同一樓梯往下走。每次不一定只走 1 級，最多可以一次跳過 3 級（即直接前進 4 級）。
但無論走多少級，1 次移動所需時間不變。兩人同時開始走，求共有多少種“兩人最終同時停在同一級”的情況（假設樓梯寬度足夠，可以相互錯開，不會撞上。另外，同時到達同一級時視為結(jié)束）。

舉個例子，有 4 級樓梯的時候，結(jié)果共有 4 種情況.

CIxmWj.png

下面是我仿照作者例子中給的代碼寫的js版本。

//走樓梯問題，遞歸方法求解.

//來寫一個復制Number類型的函數(shù)
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));

這次又不知道哪錯了？

回答
編輯回答
哚蕾咪

遞歸時尤其要注意 終止條件 和 條件分支的返回，沒有深讀你的代碼，我覺得應該是缺少了一個return

2017年5月28日 07:25
編輯回答
柚稚
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應寫在函數(shù)內(nèi)，之后，要想輸出結(jié)果，應該給函數(shù)加個返回值。

2018年8月19日 16:10