検索
ホームページウェブフロントエンドjsチュートリアル詳しい事例解説:動的プログラミング入門(階段を例に)

コンセプト

ダイナミック プログラミングはオペレーションズ リサーチの一分野であり、意思決定プロセスを最適化するための数学的手法です。
動的プログラミング アルゴリズムは通常、再帰式と 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 サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
JavaScript in Action:実際の例とプロジェクトJavaScript in Action:実際の例とプロジェクトApr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1)DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2)node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

JavaScriptとWeb:コア機能とユースケースJavaScriptとWeb:コア機能とユースケースApr 18, 2025 am 12:19 AM

Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1)DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2)ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3)サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。

JavaScriptエンジンの理解:実装の詳細JavaScriptエンジンの理解:実装の詳細Apr 17, 2025 am 12:05 AM

JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1)エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2)実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3)ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。

Python vs. JavaScript:学習曲線と使いやすさPython vs. JavaScript:学習曲線と使いやすさApr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

Python vs. JavaScript:コミュニティ、ライブラリ、リソースPython vs. JavaScript:コミュニティ、ライブラリ、リソースApr 15, 2025 am 12:16 AM

PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1)Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2)Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3)どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。

C/CからJavaScriptへ:すべてがどのように機能するかC/CからJavaScriptへ:すべてがどのように機能するかApr 14, 2025 am 12:05 AM

C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1)C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2)C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3)JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。

JavaScriptエンジン:実装の比較JavaScriptエンジン:実装の比較Apr 13, 2025 am 12:05 AM

さまざまなJavaScriptエンジンは、各エンジンの実装原則と最適化戦略が異なるため、JavaScriptコードを解析および実行するときに異なる効果をもたらします。 1。語彙分析:ソースコードを語彙ユニットに変換します。 2。文法分析:抽象的な構文ツリーを生成します。 3。最適化とコンパイル:JITコンパイラを介してマシンコードを生成します。 4。実行:マシンコードを実行します。 V8エンジンはインスタントコンピレーションと非表示クラスを通じて最適化され、Spidermonkeyはタイプ推論システムを使用して、同じコードで異なるパフォーマンスパフォーマンスをもたらします。

ブラウザを超えて:現実世界のJavaScriptブラウザを超えて:現実世界のJavaScriptApr 12, 2025 am 12:06 AM

現実世界におけるJavaScriptのアプリケーションには、サーバー側のプログラミング、モバイルアプリケーション開発、モノのインターネット制御が含まれます。 2。モバイルアプリケーションの開発は、ReactNativeを通じて実行され、クロスプラットフォームの展開をサポートします。 3.ハードウェアの相互作用に適したJohnny-Fiveライブラリを介したIoTデバイス制御に使用されます。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser は、オンライン試験を安全に受験するための安全なブラウザ環境です。このソフトウェアは、あらゆるコンピュータを安全なワークステーションに変えます。あらゆるユーティリティへのアクセスを制御し、学生が無許可のリソースを使用するのを防ぎます。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。