ダイナミックプログラミング

7487 ワード
100daysofcode memoization interview javascript テキストリンク

説明


FactorialとPascal三角形を用いた動的計画法動的計画法は、それを適用するときには非常に混乱する傾向がある概念ですが、メモ化(記憶ではない)は私のためにそれを識別する特性の一つです.コンピューティングにおいて、回想またはメモは、主に高価な機能呼び出しの結果を格納して、同じ入力が再び起こるとき、キャッシュされた結果を返すことによって、コンピュータ・プログラムをスピードアップするために主に使用される最適化技術です.

問題点:


組み合わせでパスカルの三角形を実装します.

再帰的な階乗関数


例:


    factorial de 4! =  4*3*2*1*0!
    0! = 1

記憶と再帰を伴う要因関数


function factorialDynamic() {

    let cache = new Map();

    return function factorial(n) {
        if (cache.has(n)) {
            return cache.get(n)
        } else {
            if (n <= 1) return 1;
            cache.set(n, n * factorial(n - 1));
            return cache.get(n);

    }

}
const factorial = factorialDynamic();

組合せ関数



例:
    Function: (P Q) = P! / (Q!-(P-Q)!)

function combinatorial(p, q) {
    return (factorial(p) / (factorial(q) * factorial(p - q)));
}

パスカル三角形関数



例:
Combinatorial:

fila          (p q)
0             (0 0)
1           (1 0) (1 1)
2        (2 0) (2 1) (2 2)
3     (3 0) (3 1) (3 2) (3 3)

行関数:
function row(p) {

    let row = [];

    for (let q = 0; q <= p; ++q) {
        row.push(combinatorial(p, q));
    }
    return row;

}

三角形関数( main ):


function trianglePascal(rows) {

    let triangle = [];

    for (let p = 0; p < rows; ++p) {
        triangle.push(row(p))
    }
    return triangle;
}

print funtion (テスト結果)


function print(triangle) {

    for (let row of triangle) {
        console.log(row);
    }
}
print(trianglePascal(6));

1              [ 1 ]
2             [ 1, 1 ]
3           [ 1, 2, 1 ]
4         [ 1, 3, 3, 1 ]
5       [ 1, 4, 6, 4, 1 ]
6     [ 1, 5, 10, 10, 5, 1 ]
あなたはcode by @difo23をチェックすることができます
21.08.18
ホテルの部屋割り当て-C++