検索
ホームページウェブフロントエンド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 までご連絡ください。
es6数组怎么去掉重复并且重新排序es6数组怎么去掉重复并且重新排序May 05, 2022 pm 07:08 PM

去掉重复并排序的方法:1、使用“Array.from(new Set(arr))”或者“[…new Set(arr)]”语句,去掉数组中的重复元素,返回去重后的新数组;2、利用sort()对去重数组进行排序,语法“去重数组.sort()”。

JavaScript的Symbol类型、隐藏属性及全局注册表详解JavaScript的Symbol类型、隐藏属性及全局注册表详解Jun 02, 2022 am 11:50 AM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于Symbol类型、隐藏属性及全局注册表的相关问题,包括了Symbol类型的描述、Symbol不会隐式转字符串等问题,下面一起来看一下,希望对大家有帮助。

原来利用纯CSS也能实现文字轮播与图片轮播!原来利用纯CSS也能实现文字轮播与图片轮播!Jun 10, 2022 pm 01:00 PM

怎么制作文字轮播与图片轮播?大家第一想到的是不是利用js,其实利用纯CSS也能实现文字轮播与图片轮播,下面来看看实现方法,希望对大家有所帮助!

JavaScript对象的构造函数和new操作符(实例详解)JavaScript对象的构造函数和new操作符(实例详解)May 10, 2022 pm 06:16 PM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于对象的构造函数和new操作符,构造函数是所有对象的成员方法中,最早被调用的那个,下面一起来看一下吧,希望对大家有帮助。

JavaScript面向对象详细解析之属性描述符JavaScript面向对象详细解析之属性描述符May 27, 2022 pm 05:29 PM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于面向对象的相关问题,包括了属性描述符、数据描述符、存取描述符等等内容,下面一起来看一下,希望对大家有帮助。

javascript怎么移除元素点击事件javascript怎么移除元素点击事件Apr 11, 2022 pm 04:51 PM

方法:1、利用“点击元素对象.unbind("click");”方法,该方法可以移除被选元素的事件处理程序;2、利用“点击元素对象.off("click");”方法,该方法可以移除通过on()方法添加的事件处理程序。

整理总结JavaScript常见的BOM操作整理总结JavaScript常见的BOM操作Jun 01, 2022 am 11:43 AM

本篇文章给大家带来了关于JavaScript的相关知识,其中主要介绍了关于BOM操作的相关问题,包括了window对象的常见事件、JavaScript执行机制等等相关内容,下面一起来看一下,希望对大家有帮助。

foreach是es6里的吗foreach是es6里的吗May 05, 2022 pm 05:59 PM

foreach不是es6的方法。foreach是es3中一个遍历数组的方法,可以调用数组的每个元素,并将元素传给回调函数进行处理,语法“array.forEach(function(当前元素,索引,数组){...})”;该方法不处理空数组。

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ヘンタイを無料で生成します。

ホットツール

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール