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

概要

メモリを使用して、実行時間の効率を迅速に向上させる方法

計算された結果(小さな問題)は、

の再計算を回避するために、独立したメモリ領域に格納される.

完全ナビゲーションのように非効率な時間的複雑さの問題であっても、動的プログラミングにより時間的複雑さを大幅に低減することができる.

動的プログラミングの実施は、通常、タワーと寝台の2つの方法から構成される.

ダイナミックプランニング法とも呼ばれます.
注意:一般的なプログラミング分野での動的な意味-資料構造では、動的な割り当ては「プログラムの実行中に実行に必要なメモリを割り当てる方法」を指します.動的なプログラミングでは、「動的」は意味のない言葉です.

使用条件

1.最適な局所構造
大きな問題は小さな問題に分けることができ、小さな問題の答えは集中して大きな問題を解決することができる.
2.重複する部分的な問題
同じ小さな問題は繰り返し解決しなければならない.

例:フィボナッチ数列

フィボナッチの数は以下の通りです.
1 1 2 3 5 8 13 21 34 55 89 ...
点火式
隣接するアイテム間の関係を表す
フィボナッチ数列の点火式表示
再帰関数を使用すると、点化された形式で実現できます.

実施効率の低下

public class Main {

    // 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibo(4));
    }

}

に質問

の単純な再帰関数を用いてフィボナッチ数列を解決すると,指数時間的複雑さを有する.(非効率)
┑┑┑:フィボナッチ再帰関数の指数時間複雑度
O(2^樹高N)

複数回f(2):(重複部分問題)

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

フィボナッチ数列は動的プログラミングの使用条件を満たし,動的プログラミングで有効な計算が可能である.
ダイナミックプログラミングの使用条件を満たす
1.最適な局所構造
大きな問題(ex.f(4))を小さな問題(ex.f(3)+f(2))に分けることができます.

2.重複する部分的な問題
同じ小さな問題を繰り返し解決する(ex.f(2))

タワー

実装中に再帰関数を使用する
小さな問題を再帰的に呼び出すことで大きな問題を解決
(小さな問題が解決すれば大きな問題の答えが得られる)

ページング中にメモ帳(DP)を使用して冗長性の問題を解決
✅注釈現在-計算された(小さな問題の)結果をメモリ空間に記録する方法-同じ問題を再び呼び出すと、注釈された結果が得られる-厳密には、以前計算された結果を一時的に記録する広い概念であるため、動的プログラミングに限定されない.-どうさぶんせき
a.単純再帰関数と比較して、 b.実際の呼び出し-青色:呼び出し+演算と記憶値-実線:呼び出し+直ちに返す
=>青色f(3)に以前の値が格納されているため、実線f(3)が呼び出されるが、すぐに戻るので深く入り込まない.
=>定数時間を無視(戻る)O(N)

import java.util.*;

public class Main {

    // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
    public static long[] d = new long[100];

    // 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
    public static long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환)
        if (x == 1 || x == 2) {
        	// 상수시간 소요
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            // 상수시간 소요
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

ベースフレーム

ダイナミックプログラミングの典型的な形式です.

実装中に重複文を使用
下から下へ、小さな問題を一つ一つ解決し、先に計算した問題値を利用して、次の問題に進みます.
再帰関数を使用しないため、重複する部分的な問題は発生せず、Bottom-Upは下から上へ、重複した部分的な問題についてコメントし、解答します.( リファレンス )

の再記述中に

を用いて結果リストを保存する(DP)

public class Main {

    public static long[] d = new long[100];

    public static void main(String[] args) {
        // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        d[1] = 1;
        d[2] = 1;
        int n = 50; // 50번째 피보나치 수를 계산

        // 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(d[n]);
    }
}

ダイナミックプログラミングVS分割征服

動的プログラミングおよびパーティション征服(ex.quickソート)は、いずれも最適なローカル構造を有する.
-大問題を小問題に分け、小問題の答えを集約して大問題を解決する場合

動的プログラミングとセグメント征服の違いは、局所的な問題があるかどうかである.

動的プログラミング問題において、各部分の問題は相互に影響し、一部の問題は

を繰り返す.

分割征服問題同じ部分の問題を繰り返し計算しない

動的プログラミングの問題の処理方法

与えられた問題が動的プログラミングタイプであることを決定することは重要である

について質問されると、まず、図面、実装、完全なナビゲーションなどの考え方によって問題を解決できるかどうかを考慮することができる.
-他のアルゴリズムで解くことができない場合は、動的プログラミングを考慮しましょう.

再帰関数を使用して、非効率な完全なナビゲーションプログラムを記述し、小さな問題の答えが大きな問題で依然として利用可能である場合、注釈転送機能を使用してコード

を改善する.

は、一般的なテープレベルで基本的なタイプの動的プログラミング問題

を提起する.