Kadaneのアルゴリズムにおける動的プログラミングの側面

Question

私は上記のアルゴの最適な基礎構造と重複する問題（パンとバターのDP）の理解に誰も助けてくれますか？

Answer 1

重複部分問題のthis定義によれば、Kadaneのアルゴリズム（f[i] = max(f[i - 1] + a[i], a[i])）の再帰的な製剤は、この性質を示しません。各サブ問題は、単純な再帰的実装で1回だけ計算されます。

しかしその定義hereに応じて最適な下部を示さない：我々は（f[i]がf[i - 1]を使用しています）私たちの与えられた問題への解決策を見つけるために小さな部分問題へのソリューションを使用しています。

は、動的プログラミングの定義here考えてみましょう：数学、コンピュータサイエンス、および経済学で

を、ダイナミックプログラミングは単純な部分問題にそれらを分解することで、複雑な問題を解決するための方法です。重複するサブ問題の性質を示す問題に適用可能であり、最適サブ構造（後述）。適用可能であれば、この方法は、深さ優先検索のような部分問題の重なりを利用しない素朴な方法よりもはるかに短い時間を要する。

ダイナミックプログラミングの背後にあるアイデアは非常に簡単です。一般に、与えられた問題を解決するためには、問題の異なる部分（部分問題）を解決し、部分問題の解決策を組み合わせて全体的な解決策に到達する必要があります。多くの場合、より素朴な方法を使用すると、多くの部分問題が生成され、何度も解決されます。それは破壊することによって問題を解決しない：動的計画法は、このような計算

これはKadaneのアルゴリズムは、DPアルゴリズムとみなすことができるか否かの解釈の余地の数を減らし、一度だけ、各部分問題を解決しようとしますそれはより簡単なサブ問題になりますが、そのコア再帰的アプローチは、DPが効率的に処理するためのものである重複するサブ問題を生成しないため、DPの専門外に置くことになります。一方、基本的な再帰的アプローチがサブ問題をオーバーラップさせる必要はないと言えるかもしれませんが、再帰的アルゴリズムはDPアルゴリズムになります。これはDPに私の意見。しかし、私は文章の中でこれを確実に解決するものは何も知らないので、生徒に印を付けたり、本や記事をラベル付けしたりすることはしません。

私はDPアルゴリズムではなく、実装に応じて貪欲で再帰的なアルゴリズムだと言います。私は上記の理由からアルゴリズム的な観点からは貪欲であると言いますが、客観的には他の解釈も有効と考えています。