末尾再帰を使用してフィボナッチ数をプログラミングしていましたが、その背後にある考え方は動的プログラミングと同じようです。それで、それらは同じですか？むしろ、それらの間にある程度の類似性がありますか？そうでない場合、それらが異なる場合はいつですか？
2218 次
3 に答える
3
用語自体は関連していますが、決して同等ではありません。
動的計画法は、末尾再帰を使用して、または使用せずに実装できる問題解決方法です。より一般的には、「メモ化」が必要です。
末尾再帰は、メモ化ロジックを特定のフィールドに具体的に適用するため、動的計画法アルゴリズムを実装するための一般的な方法です。
于 2012-09-30T00:29:57.680 に答える
1
あなたがこの質問をしている理由がわかります。動的計画法の背後にある考え方は、問題をより小さな問題に分割することです。これは、多くの再帰的 (末尾であろうとなかろうと) 関数の背後にある考え方とまったく同じです。
これは本当にリンゴとオレンジのような比較であり、多くの良い答えがありますが、2 つのアイデアを比較するのが非常に難しい理由を理解させる 1 つのことがあります: Java を含む一部の言語では、技術的に末尾再帰を使用できません。 . ご存じかもしれませんが、末尾再帰関数は呼び出しの結果のスタックを保存して後で使用するわけではありません。ただし、Java では、メソッド呼び出しごとにスタック トレースが維持されます。これはスタック スペースを使用し、実行回数が多すぎるとスタック オーバーフローが発生する可能性があります。したがって、末尾再帰的に見える Java メソッドは、実際にはそうではありません。
于 2012-09-29T05:12:26.030 に答える
0
動的計画法は、通常、末尾再帰によって行われるのと同じタスクを行うためのより効果的な方法です。主な違いは、動的計画法は既に計算された結果を保存するため、同じ操作が発生した場合、コードが再度実行される代わりに、値が単純に検索されることです。これはより多くのスペース/メモリを消費しますが、アルゴリズムはより高速になります。
フィボナッチの場合、動的計画法の解決策は、配列の最後の 2 つの要素を常に追加して、次の要素を取得することです。末尾再帰ソリューションは、フィボナッチの各値をゼロから計算します。
于 2012-09-29T04:46:03.193 に答える