私は、競争の激しいプログラミングに挑戦しようとしている初学年のCSC学生です。すべての再帰アルゴリズムを動的プログラミングで改善できますか？
再帰には、サブ問題の定義と解決が含まれます。私が理解しているように、トップダウンダイナミックプログラミング（dp）は、アルゴリズムの時間の複雑さを減らすために、サブ問題に対する解法をメモすることです。
の効率を向上させるためにトップダウンdpを使うことができます。サブ問題が重複している再帰アルゴリズム？どこでdpがうまく動作せず、これをどのように識別できますか？
短い答えは：はい。
ただし、いくつかの制約があります。最も明白なのは、再帰呼び出しが重複しなければならないということです。私。アルゴリズムの実行中に、再帰関数を同じパラメーターで複数回呼び出す必要があります。これにより、メモ生成によって再帰ツリーを切り捨てることができます。したがって、いつもメモの数を減らして通話回数を減らすことができます。
ただし、この通話の減額には価格が付いています。結果をどこかに保存する必要があります。次の明らかな制約は、十分なメモリが必要であるということです。これには明らかでない制約があります。メモリアクセスには常に時間がかかります。最初に結果が格納されている場所を見つけて、それをある場所にコピーする必要があります。したがって、場合によっては、再帰が結果をどこかから読み込むのではなく、計算するのがより速いかもしれません。しかし、これは実装固有のものであり、オペレーティングシステムやハードウェアの設定にも依存します。