再帰と動的プログラミング

Question

動的プログラミングを使用して解決できるすべてのプログラムは再帰を使用して解決できますが、逆も可能です。可能であれば、時間の複雑さはどのように異なるでしょうか？

Answer 1

も同じですか？

はい。一方

、あなたが実際に依頼することを意味している場合：

も真逆もまた同様ですか？

それでは答えはいいです。再帰的アルゴリズムで解決できる問題のすべては、動的プログラミングでは合理的に解決できるわけではありません。これを強調するために、並べ替えるという1つの問題だけを考え出す必要があります。再帰アルゴリズムでソートの問題を解決するのは簡単ですが、動的プログラミングによるソートの問題を解決するための合理的なアルゴリズムはないようです。残念ながら、ここでは「妥当な」ウィーゼル語を使うことに頼らざるを得ません。なぜなら、ソートの問題を何らかの方法でダイナミックにプログラミングして、非常に扱いにくく非効率的な方法で使用できるからです。

時間の複雑さに関するご質問にはお答えできません。これは手元の問題と、どのように適用可能な動的プログラミングが問題を解決するかにかかっています。

Answer 2

ダイナミックプログラミングは、時間と複雑さのトレードオフです。いくつかの情報をテーブルに保存するので、同じことをやり直す必要がある場合は、情報を再計算する必要はありません。

問題が自然発生的にサブプログラムに分解され、頻繁に繰り返すと、動的プログラミングが良い考えです。一方、再帰的な問題がなければ、動的プログラミングを使用することに意味はありません。