ワインの選択動的プログラミング

Question

これはDPを実装するのにはかなり有名な例ですが、何らかの理由で私はアルゴリズムを完全に理解することができず、かなり長い間（olympiadを計算するために）執着しています。問題は次のとおりです

棚には、N個のワインが並んでいるとします。わかりやすくするために、左から右へワイン番号をつけましょう。 は、1からNまでの整数、それぞれ で棚に立っています。 i番目のワインの価格はpiです（異なるワインの の価格は異なる場合があります）。

今日は年間とすると、i番目のワインの価格はy * piになります。つまり、今年度の の値のy倍になります。

あなたはすべてのワインを売りたいが、今年からは1年に1本のワインを正確に 販売したいと思う。もう1つの制約 - の場合、一番左のワインまたは 右のワインのみを棚に置いて販売することが許可されており、 ワインを棚に並べ替えることはできません（つまり、最初は ）。

あなたは何を最適な順序で

をワインを販売 場合、あなたが得ることができる最大の利益であるとC++での溶液をメモ化と解決策があります（与えられたが、ことをされて、知りたいですほとんど）私の疑問事項ません：

int p[N]; // read-only array of wine prices 


// year represents the current year (starts with 1) 
// [be, en] represents the interval of the unsold wines on the shelf 
int profit(int year, int be, int en) { 
    // there are no more wines on the shelf 
    if (be > en) 
    return 0; 
    // try to sell the leftmost or the rightmost wine, recursively calculate the 
    // answer and return the better one 
    return max(
    profit(year+1, be+1, en) + year * p[be], 
    profit(year+1, be, en-1) + year * p[en]); 
} 

私が持っている主な混乱は、最大（）関数に関連して、我々はこれまで私が理解できるようusing.Asあり、再帰的な利益（）関数は、総どうなるか計算し昨年ワイン1を販売した場合の利益と、私たちが去年にワイン2を売ったのならば、それは後の年に売られたワイン1がもっと大きい総利益を持っていると言うことができるので、実際にワイン1を保つべきではありません。 ）、ワイン2を売る（それはワイン1よりも利益が少ない）、あるいは私が得られないものがあるか？

Answer 1

この再帰的な解決策は、すべての可能なシーンをチェックし、その最大値を返すことです。いくつかの分析、2つの可能なconiditionは右または左のeverystepを選ぶことができるので、あなたのアルゴリズムは本当に遅いO（2^n）を働かせます。 max（）は本当に大きなものを選択するためのものです。そしてこの解決法は動的ではありません。あなたはMemoization：https://en.wikipedia.org/wiki/Memoizationを使うことができます。

return max( 
profit(year+1, be+1, en) + year * p[be], 
profit(year+1, be, en-1) + year * p[en]); 

でも同様です。

int max_from_left = profit(year+1, be+1, en) + year * p[be] 

int max_from_right = profit(year+1, be, en-1) + year * p[en]); 

if(max_from_left > max_from_right) 
    return max_from_left 
else 
    return max_from_right 

Answer 2

私の知る限り理解できるように、再帰的な利益（）関数は、昨年にワイン1を売却し、私たちはワイン2を売却した場合、何が総利益になるならば、総利益がどうなるかを計算昨年。それで、ワイン1がより多くの総利益を持っていると言うことができます。もしそれが後で売れば、実際にワイン1を保つべきではありません。少ないワイン1より利益）

それが今年1年1かワイン販売ワイン1「最後」とどうどのような計算なしの完全に間違って、その再帰的なアルゴリズム、uは（10ワインの最大を持って想像）します次の10年間計算して答えを返してください