搜尋此網誌

2012年2月27日 星期一

Dynamic Programming(動態程式規劃)

Dynamic Programming : 主要概念是把複雜的大問題,切割成多個小問題,然後把這些小問題的答案組合出一個較完成的答案, 來解答大問題. 若列舉出所有答案的排列組合,很花時間而且會做很多多餘且重複不必要的計算, 使用動態程式設計可以減少許多不必要的計算時間和次數.

以下用找出陣列元素總合為最大值的子陣列來做解釋

Maximum Subarray Problem: