Re: [討論] 令人印象深刻的遞迴問題？

[Ohwil ( )]

※ 引述《yauhh (喲)》之銘言：
: ※ 引述《purpose (purpose)》之銘言：
: : 看到有人在板上找遞迴題目，說要拿來練習。
: : 這讓我想到以前上課時，學校老師提過一個考古題，關於股票買賣的：
: :         若有某公司的股價 double price[] = {55.39, 109.23, 48.29, 81.59,
: :                                            81.58, 105.53, 94.45, 12.24};
: :         其中 55.39 表示第一天的價格、109.29 為第二天的價格。
: :         不能在同一天同時進行購買與販賣。
: :         寫一個「遞迴函數」，用來求出獲利最大的買賣方式。
: : 當初想很久都沒想到，看到公佈的答案後，又覺得確實合理，所以讓我印象深刻。

假設前面n個存在一個比較好的交易

第i個時間買si 第k個時間賣sk,  價差sk-si   k>i

檢查第n+1個時間點是否可以賣

(不考慮買,因為你不知道會不會有n+2的時間點)

(如果可以賣,就把i,k的值換掉)

只要在前面n個多存一個最小值 min_n   就可以達到O(n)

應該就是遞迴的思考了吧？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 223.139.161.188
→ firejox:其實是DP (誤
→ yauhh:雖然可以說像DP,但DP也是遞迴解
→ firejox:memorization 才是遞迴 DP 是bottom up
→ yauhh:不對,DP本身只是優化技巧,底子是遞迴就是遞迴
→ yauhh:而且遞迴也是bottom up,所以才會分base和recursive cases
→ yauhh:通常講DP並不意指它不是遞迴. 這個跟那個事兩回事. 不過以
→ firejox:喔喔 我了解了
→ yauhh:這題寫到O(n)層次的寫法,的確已經是DP了.