C++ の動的プログラミング アルゴリズムとその応用スキル

ダイナミック プログラミング (DP) は、重複する部分問題と最適な部分構造プロパティを含むいくつかの問題を解決するために使用される効率的なアルゴリズムです。 C 言語で動的プログラミング アルゴリズムを実装する場合、効率を向上させるためのテクニックがいくつかあります。この記事では、C の動的プログラミング アルゴリズムとその応用テクニックを紹介します。

動的計画アルゴリズムの主な考え方は、問題を一連のサブ問題に分解し、各サブ問題を解決するときに状態を保持し、この状態を使用して計算の繰り返しを避けることです。動的計画アルゴリズムは、各部分問題を毎回ではなく 1 回だけ計算するだけで済むため、計算コストのかかる問題を解決できます。

1. 動的計画法の 3 つの要素

動的計画法アルゴリズムは、次の 3 つの要素を満たす必要があります。

(1) 最適な部分構造:問題 最適解には、その部分問題に対する最適解が含まれています。

(2) 後遺症なし: プロセス内のすべての状態は現在の状態にのみ関連し、以前の状態とは何の関係もありません。

(3) サブ問題のオーバーラップ: 複数のサブ問題が互いにオーバーラップするため、計算の繰り返しを回避できます。

2. 動的プログラミングの基本分類

動的プログラミングには 2 つの基本分類があります。1 つは状態ベースの動的プログラミングで、もう 1 つは意思決定ベースの動的プログラミングです。状態ベースの動的プログラミングとは、計算中に各部分問題の解を保存し、これらの解の値に基づいてより大きな問題の解を計算することを指します。状態は通常、配列などのデータ構造を使用して保存されます。意思決定ベースの動的プログラミングとは、計算中に各部分問題の最適解に基づいて、より大きな問題に対する最適解を決定することを指します。この方法は、最適化問題を解く場合や最小値を計算する場合によく使用されます。

3. 動的プログラミングのアプリケーション スキル

C で動的プログラミング アルゴリズムを実装する場合、効率を向上させることができるアプリケーション スキルがいくつかあります。これらの手法には次のようなものがあります。

(1) 配列添字の代わりに定数を使用します。一部の動的プログラミングの問題では、配列への複数回のアクセスが必要です。このとき、配列の添え字を定数に置き換えることで、アクセスを高速化できます。例:

for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

変数 k を使用して dp 配列の添え字を置き換えることができます:

for(int k=2;k<=n+m;k++){
    for(int i=1;i<=n;i++){
        int j = k-i;
        if(j<1 || j>m) continue;
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

(2) 配列を最適化します: 動的計画法の問題によっては、配列のサイズが非常に大きいため、メモリ制限が発生する可能性があります。このとき、ローリング配列または 2 次元配列の最初の次元を使用して、中間結果を保存できます。例:

int dp[N][M];
for(int i=0;i<N;i++){
    for(int j=0;j<M;j++){
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])+1;
    }
}

は次のように最適化できます:

int dp[2][M];
for(int i=0;i<N;i++){
    int cur = i%2, pre = (i+1)%2;
    for(int j=0;j<M;j++){
        dp[cur][j] = max(dp[pre][j],dp[cur][j-1])+1;
    }
}

(3) スペースの節約: 一部の動的プログラミングの問題では、配列全体ではなく、最新の状態のみを保存する必要があります。この時点で、スクロール配列を使用して、最新の状態のみを保存できます。

(4) 計算の繰り返しを避ける: 動的計画法の問題によっては、部分問題が繰り返される場合があります。このとき、記憶された検索またはボトムアップ動的プログラミングを使用して、計算の繰り返しを避けることができます。

4. 動的計画法の例

動的計画法の問題の例をいくつか示します。

(1) フィボナッチ数列: フィボナッチ数列とは、開始することを意味します。 0 と 1 の各数値は、前の 2 つの数値の合計に等しくなります。たとえば、0、1、1、2、3、5、8、13、21。

再帰式は次のとおりです: f[n] = f[n-1] f[n-2]

動的計画アルゴリズムを使用すると、次のことが実現できます:

int dp[N];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
    dp[i] = dp[i-1] + dp[i-2];
}

(2) ナップザック問題: ナップザック問題は、N 個のアイテムがあり、各アイテムには重さと値があることを意味します。ナップザックの容量Cが与えられたとき、ナップザックの容量を超えずに積載できる最大値を求めます。

動的プログラミング アルゴリズムを使用すると、次のことを実現できます:

int dp[N][C];
for(int i=0;i<N;i++){
    for(int j=0;j<C;j++){
        dp[i][j] = 0;
    }
}
for(int i=0;i<N;i++){
    for(int j=0;j<=C;j++){
        if(j>=w[i]){
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
        else{
            dp[i][j] = dp[i-1][j];
        }
    }
}

上記は、動的プログラミング アルゴリズムと C でのその応用スキルの簡単な紹介です。複雑な動的計画法の問題では、時間計算量と空間計算量も考慮する必要があります。したがって、動的計画アルゴリズムを実装する場合は、さまざまな要素を考慮して適切な方法を選択する必要があります。

以上がC++ の動的プログラミング アルゴリズムとその応用スキルの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。