動的プログラミングは、問題をサブ問題に分割し、結果を再度計算する必要がないように、将来の目的のために結果を保存する手法です。部分問題は全体的な解を最適化するために最適化され、最適部分構造プロパティとして知られています。動的プログラミングの主な用途は、最適化問題を解決することです。ここでの最適化問題とは、問題の最小または最大の解決策を見つけようとするときのことを意味します。動的プログラミングでは、解決策が存在する場合、問題の最適な解決策を見つけることが保証されます。

動的プログラミングの定義によれば、動的計画は、最初に単純な部分問題の集合に分割し、各部分問題を 1 回だけ解決し、その後、繰り返しの計算を避けるためにその解を保存することによって、複雑な問題を解決する手法であるとされています。

例を通してこのアプローチを理解しましょう。

フィボナッチ数列の例を考えてみましょう。次の系列はフィボナッチ数列です。

C++ セット

0、1、1、2、3、5、8、13、21、34、55、89、144、、…

上記の系列の数値はランダムに計算されたものではありません。数学的には、次の式を使用して各項を書くことができます。

F(n) = F(n-1) + F(n-2)、

基本値は F(0) = 0、F(1) = 1 です。他の数値を計算するには、上記の関係に従います。たとえば、F(2) は合計です。 f(0) そして f(1)、 これは 1 に等しい。

F(20) はどのように計算できますか?

F(20) 項は、フィボナッチ数列の n 次式を使用して計算されます。以下の図は、F(20) がどのように計算されるかを示しています。

Javaは乱数を生成します

上の図からわかるように、F(20) は F(19) と F(18) の合計として計算されます。動的プログラミングのアプローチでは、問題を同様のサブ問題に分割しようとします。上記のケースでは、F(20) が同様の部分問題、つまり F(19) と F(18) に入るこのアプローチに従っています。動的計画法の定義を要約すると、同様の部分問題を複数回計算すべきではないということになります。それでも、上記の場合、部分問題は 2 回計算されます。上の例では、F(18) が 2 回計算されます。同様に、F(17) も 2 回計算されます。ただし、この手法は同様の部分問題を解決するため非常に便利ですが、一度計算した結果を保存することにこだわっていないため、結果を保存する際には注意が必要であり、リソースの無駄遣いにつながる可能性があります。

上の例では、右側のサブツリーで F(18) を計算すると、リソースが大量に使用され、全体的なパフォーマンスが低下します。

上記の問題の解決策は、計算結果を配列に保存することです。まず、F(16) と F(17) を計算し、それらの値を配列に保存します。 F(18) は、すでに配列に保存されている F(17) と F(16) の値を合計することによって計算されます。 F(18) の計算値は配列に保存されます。 F(19) の値は、F(18) と F(17) の合計を使用して計算され、それらの値はすでに配列に保存されています。 F(19) の計算値は配列に格納されます。 F(20) の値は、F(19) と F(18) の値を加算することで計算でき、F(19) と F(18) の値は両方とも配列に格納されます。 F(20) の最終計算値は配列に格納されます。

動的プログラミングのアプローチはどのように機能するのでしょうか?

動的プログラミングが実行する手順は次のとおりです。

• 複雑な問題をより単純な部分問題に分解します。
• これらの副次的な問題に対する最適な解決策を見つけます。
• 部分問題の結果を保存します (メモ化)。部分問題の結果を保存するプロセスは、記憶として知られています。
• それらを再利用して、同じサブ問題が複数回計算されるようにします。
• 最後に、複雑な問題の結果を計算します。

上記の 5 つのステップは、動的プログラミングの基本的なステップです。動的プログラミングは、次のようなプロパティを持つものに適用できます。

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

重複する部分問題と最適な部分構造を持つ問題。ここで、最適部分構造とは、すべての部分問題の最適解を単純に組み合わせることで最適化問題の解が得られることを意味する。

動的プログラミングの場合、中間結果を保存するときに空間の複雑さは増加しますが、時間の複雑さは減少します。

動的計画法のアプローチ

動的プログラミングには 2 つのアプローチがあります。

• トップダウンアプローチ
• ボトムアップアプローチ

トップダウンアプローチ

トップダウンのアプローチは暗記法に従い、ボトムアップのアプローチは表作成法に従います。ここで、記憶は再帰とキャッシュの合計に等しいです。再帰は関数自体を呼び出すことを意味し、キャッシュは中間結果を保存することを意味します。

利点

npmクリーンキャッシュ

• 理解して実装するのは非常に簡単です。
• 必要な場合にのみサブ問題を解決します。
• デバッグは簡単です。

短所

呼び出しスタック内でより多くのメモリを占有する再帰手法が使用されます。再帰が深すぎると、スタック オーバーフロー状態が発生することがあります。

より多くのメモリを占有するため、全体的なパフォーマンスが低下します。

例を通して動的プログラミングを理解しましょう。

 int fib(int n) { if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); } < pre> <p>In the above code, we have used the recursive approach to find out the Fibonacci series. When the value of &apos;n&apos; increases, the function calls will also increase, and computations will also increase. In this case, the time complexity increases exponentially, and it becomes 2<sup>n</sup>.</p> <p>One solution to this problem is to use the dynamic programming approach. Rather than generating the recursive tree again and again, we can reuse the previously calculated value. If we use the dynamic programming approach, then the time complexity would be O(n).</p> <p>When we apply the dynamic programming approach in the implementation of the Fibonacci series, then the code would look like:</p> <pre> static int count = 0; int fib(int n) { if(memo[n]!= NULL) return memo[n]; count++; if(n<0) error; if(n="=0)" return 0; 1; sum="fib(n-1)" + fib(n-2); memo[n]="sum;" } < pre> <p>In the above code, we have used the memorization technique in which we store the results in an array to reuse the values. This is also known as a top-down approach in which we move from the top and break the problem into sub-problems.</p> <h3>Bottom-Up approach</h3> <p>The bottom-up approach is also one of the techniques which can be used to implement the dynamic programming. It uses the tabulation technique to implement the dynamic programming approach. It solves the same kind of problems but it removes the recursion. If we remove the recursion, there is no stack overflow issue and no overhead of the recursive functions. In this tabulation technique, we solve the problems and store the results in a matrix.</p> <p>There are two ways of applying dynamic programming:</p> <ul> <tr><td>Top-Down</td>  </tr><tr><td>Bottom-Up</td>  </tr></ul> <p>The bottom-up is the approach used to avoid the recursion, thus saving the memory space. The bottom-up is an algorithm that starts from the beginning, whereas the recursive algorithm starts from the end and works backward. In the bottom-up approach, we start from the base case to find the answer for the end. As we know, the base cases in the Fibonacci series are 0 and 1. Since the bottom approach starts from the base cases, so we will start from 0 and 1.</p> <p> <strong>Key points</strong> </p> <ul> <li>We solve all the smaller sub-problems that will be needed to solve the larger sub-problems then move to the larger problems using smaller sub-problems.</li> <li>We use for loop to iterate over the sub-problems.</li> <li>The bottom-up approach is also known as the tabulation or table filling method.</li> </ul> <p> <strong>Let&apos;s understand through an example.</strong> </p> <p>Suppose we have an array that has 0 and 1 values at a[0] and a[1] positions, respectively shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-2.webp" alt="Dynamic Programming"> <p>Since the bottom-up approach starts from the lower values, so the values at a[0] and a[1] are added to find the value of a[2] shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-3.webp" alt="Dynamic Programming"> <p>The value of a[3] will be calculated by adding a[1] and a[2], and it becomes 2 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-4.webp" alt="Dynamic Programming"> <p>The value of a[4] will be calculated by adding a[2] and a[3], and it becomes 3 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-5.webp" alt="Dynamic Programming"> <p>The value of a[5] will be calculated by adding the values of a[4] and a[3], and it becomes 5 shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-6.webp" alt="Dynamic Programming"> <p>The code for implementing the Fibonacci series using the bottom-up approach is given below:</p> <pre> int fib(int n) { int A[]; A[0] = 0, A[1] = 1; for( i=2; i<=n; i++) { a[i]="A[i-1]" + a[i-2] } return a[n]; < pre> <p>In the above code, base cases are 0 and 1 and then we have used for loop to find other values of Fibonacci series.</p> <p> <strong>Let&apos;s understand through the diagrammatic representation.</strong> </p> <p>Initially, the first two values, i.e., 0 and 1 can be represented as:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-7.webp" alt="Dynamic Programming"> <p>When i=2 then the values 0 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-8.webp" alt="Dynamic Programming"> <p>When i=3 then the values 1and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-9.webp" alt="Dynamic Programming"> <p>When i=4 then the values 2 and 1 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-10.webp" alt="Dynamic Programming"> <p>When i=5, then the values 3 and 2 are added shown as below:</p> <img src="//techcodeview.com/img/daa-tutorial/79/dynamic-programming-11.webp" alt="Dynamic Programming"> <p>In the above case, we are starting from the bottom and reaching to the top.</p> <hr></=n;></pre></0)></pre></0)>