動的プログラミングまたは DP - TECHCODEVIEW.COM

動的プログラミング は、複雑な問題をより単純な部分問題に分割することで解決するために、数学とコンピューターサイエンスで使用される方法です。各部分問題を 1 回だけ解決して結果を保存することで、冗長な計算が回避され、幅広い問題に対するより効率的な解決策が得られます。この記事では、例を示しながら動的プログラミングの概念を詳しく説明します。

C++ セット

動的プログラミング

動的プログラミングとは何ですか?
動的プログラミングはどのように機能するのでしょうか?
動的プログラミングの例
動的プログラミングをいつ使用するか?
動的プログラミングのアプローチ
動的プログラミングアルゴリズム
動的プログラミングの利点
動的計画法の応用
動的プログラミングの基礎を学ぶ
動的プログラミングの高度な概念
動的プログラミングの問題

動的プログラミング (DP) とは何ですか?

動的プログラミング (DP) は、複雑な問題をより単純な部分問題に分割することで解決するために、数学とコンピューターサイエンスで使用される方法です。各部分問題を 1 回だけ解決して結果を保存することで、冗長な計算が回避され、幅広い問題に対するより効率的な解決策が得られます。

動的プログラミング (DP) はどのように機能しますか?

副次的な問題を特定します。 主な問題を、より小さな独立したサブ問題に分割します。
ストアソリューション: 各部分問題を解決し、その解をテーブルまたは配列に保存します。
ソリューションを構築する: 保存されている解決策を使用して、主要な問題の解決策を構築します。
冗長性を避ける: DP は解を保存することで、各部分問題が 1 回だけ解決されるようにし、計算時間を短縮します。

動的プログラミング (DP) の例

例 1: フィボナッチ数列を見つける問題を考えてみましょう。

フィボナッチ数列: 0、1、1、2、3、5、8、13、21、34、…

ブルートフォースアプローチ:

ブルートフォースアプローチを使用して n 番目のフィボナッチ数を見つけるには、単に次の値を追加します。 (n-1) 番目 そして (n-2)番目 フィボナッチ数。これは機能しますが、値が大きい場合は非効率的になります。 n 、以前のすべてのフィボナッチ数を計算する必要があるためです。

動的プログラミングのアプローチ:

動的計画法を使用したフィボナッチ数列

副次的な問題: F(0)、F(1)、F(2)、F(3)、…
ストアソリューション: 計算された F(n) の値を保存するテーブルを作成します。
ソリューションを構築する: F(n) については、テーブル内の F(n-1) と F(n-2) を検索して加算します。
冗長性を避ける: このテーブルにより、各部分問題 (F(2) など) が 1 回だけ解決されることが保証されます。

DP を使用すると、部分問題を再計算することなく、フィボナッチ数列を効率的に計算できます。

Javaは乱数を生成します

例 2: 最長共通部分列 (2 つの文字列に共通する最長部分列を見つける)

例 3: グラフ内の最短パス (グラフ内の 2 つのノード間の最短パスを見つける)

例 4: ナップザック問題（与えられた容量のナップザックに入れることができるアイテムの最大値を求める）

動的プログラミング (DP) をいつ使用するか?

動的プログラミングは、次の特性からなる問題を解決するときに使用される最適化手法です。

1. 最適な下部構造:

最適な部分構造とは、部分問題の最適な結果を組み合わせて、より大きな問題の最適な結果を達成することを意味します。

Javaでの整数から文字列への変換

例：

を見つける問題を考えてみましょう。 最低コスト からの加重グラフ内のパス ソース ノードから 行き先 ノード。この問題は、次のような小さなサブ問題に分解できます。

を見つける最小料金からのパス ソース それぞれへのノード中級ノード。

を見つける最小料金それぞれからの道のり中級ノードへの 行き先 ノード。

より大きな問題の解決策 (ソースノードから宛先ノードまでの最小コストパスを見つける) は、これらの小さなサブ問題の解決策から構築できます。

2. 重複する副問題:

同じ部分問題が、問題の異なる部分で繰り返し解決されます。

例：

を計算する問題を考えてみましょう。 フィボナッチ数列 。インデックスでフィボナッチ数を計算するには n 、インデックスのフィボナッチ数を計算する必要があります n-1 そして n-2 。これは、インデックスでのフィボナッチ数を計算する部分問題が次のことを意味します。 n-1 インデックスでのフィボナッチ数を計算するというより大きな問題の解決策で 2 回使用されます。 n 。