詳しい事例解説：動的プログラミング入門（階段を例に）

コンセプト

ダイナミック プログラミングはオペレーションズ リサーチの一分野であり、意思決定プロセスを最適化するための数学的手法です。
動的プログラミング アルゴリズムは通常、再帰式と 1 つ以上の 初期状態に基づいています。 現在の 部分問題の解は、前の部分問題の解から 導出されます。

基本的な考え方

特定の問題を解決するには、そのさまざまな部分を解決し (つまり、サブ問題を解決する)、次にサブ問題の解決策を組み合わせて、元の問題の解決策を得る必要があります。
通常、多くの部分問題は非常に似ているため、動的計画法では 各部分問題を 1 回だけ解決しようとします。これにより、計算量が削減されます。
特定の部分問題の解が計算されると、メモリに保存されるので、次回同じ部分問題の解が必要になったときにテーブルを直接検索できます。
このアプローチは、反復される部分問題の数が入力のサイズに応じて指数関数的に増加する場合に特に役立ちます。
動的プログラミングには 3 つの主要な要素があります:
1. 最適部分構造
2. 境界
3. 状態遷移方程式

問題を見てみましょう

高さ 10 段の階段があります。上に歩くと、各ステップは 1 つまたは 2 つしか上がりません。合計で何手あるかを求めます。

例えば、1歩ずつ、合計10歩歩くのも歩き方の一つです。

別の例は、毎回 2 歩、合計 5 歩歩くこれも歩き方です。

でも、これを一つ一つやるのは面倒なので、次のように最後の一歩をどうするか考えてみましょう

10番目の階段に行く方法 = 8番目の階段に行く + に行く9 番目の階段

n 番目の階段に到達する方法を表すために f(n) を使用するため、f(10) = f(9) + f(8) となります

f(9) = f(8) + f( 7), f(8) = f(7) + f(6)....

このようにして、

再帰式

を取得します: f(n) = f(n-1 ) + f(n-2);
2 つの初期状態もあります
:f(1) = 1;
f(2) = 2;
これにより、最初の状態が得られます。 1: 再帰的解法

function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    return getWays(n-1) + getWays(n-2); 
}

このメソッドの時間計算量は

O(2^n)

これが二分木であることがわかり、ノードの数が再帰の回数です方程式を計算する必要があり、数値の高さは N、ノードの数は約 2^n
であるため、時間計算量は約 O(2^n)

ですが、この方法は最適化できますか?

下の図に示すように、いくつかの値が繰り返し計算されていることがわかります

同じ色が繰り返し部分を表しているため、これらの繰り返し計算された値を

記録

できますか?
そのような最適化には 2 番目の方法があります
方法 2: メモ アルゴリズム

const map = new Map(); 
function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    if (map.has(n)) {
        return map.get(n);
    }
    const value = getWays(n-1) + getWays(n-2);
    map.set(n, value);
    return value; 
}

n-2 のキーと値のペアが最終的にマップに格納されるため、空間複雑度は

O(n)

、時間複雑さも

O(n)

これが最適解なのか考え続けます。 元の考え方に戻り、前の階段を歩いたと仮定し、最後のステップのみを考慮すると、 f(n) = f(n-1) + f(n- という再帰式が得られます。 2) 、これはトップダウンの解決策です 一般的に言えば、通常の考え方によれば、ボトムアップで解決する必要があります。

これは、最初の 1 つと 2 つの階段のステップ数です。これは、前に述べたように

初期状態です

。これは、3 つの階段のステップ数、f を取得するための反復です。 (3 ) は f(1) と f(2) にのみ依存します次のステップを見てください

ここで別の反復が実行されて階段の 4 ステップが取得されます。f(4) は f(2) にのみ依存します) と f (3)

各反復には最初の 2 つの反復のデータのみが必要であり、すべてのサブ状態のデータをメモのように保存する必要がないことがわかりました

方法 3: 動的プログラミング ソリューション

function getWays(n) {

    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;

    // a保存倒数第二个子状态数据，b保存倒数第一个子状态数据， temp 保存当前状态的数据
    let a = 1, b = 2;
    let temp = a + b;
    for (let i = 3; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp; 
    }
    return temp; 
}

これが私たちがもう一度見ることができるものです現在の時間計算量と空間計算量

現在の時間計算量はまだ

O(n)

ですが、空間計算量は

O(1)

に減少しますこれは理想的な結果です概要これは単なる動的プログラミングです。変更次元が 1 つしかないため、世界で最も単純な問題の 1 つです。
変更次元が 2 つ、3 つ、あるいはそれ以上になると、ナップザック問題はより複雑になります。典型的な多次元の問題です。興味があれば、オンラインで「バックパッキングに関する 9 つの講義」をご覧ください。

関連する推奨事項:

JS動的プログラミングの使用方法の詳細な説明

JavaScriptの高度なアルゴリズム動的プログラミングのサンプル分析

以上が詳しい事例解説：動的プログラミング入門（階段を例に）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。