動態規劃的推廣
我對動態規畫（ Dynamic Programming ）的認識起於奧林匹亞研習營，有一次的專題便是動態規畫，其主要的內容是說在解決某些問題時，要求的答案其值決定於前面的值，而「前面」的值又決定於更前面的值。於是須要從前面一步一步的求值。
\r 舉一個簡單的例：費氏數列在數學上定義成
\r f(0)=1
\r f(1)=1
\r f(x)=f(x-1)+f(x-2)
\r 如果需要寫一個程式來計算的話，直覺的方法便是依照原本的定義，用遞迴來解決：
\r int=f(intx)
\r {
\r if(x \r returen f(x-1)+f(x-2);
\r }
\r \r 若要計算 f ( 5 ）的話，其過程可由右圖來表示。 f ( 5 ）的值取決於 ft4 ）及 f ( a ) , f ( 4 ) 的值取決於 f ( 3 ）及 f ( 2 ) ，這裡我們可以發現到， f ( a ）在 f ( s ）及 f ( 4 ）中分別計算了一次，這便是浪費。再看得更詳細一點， f ( l ）計算了 5 次， f ( 0 ）計算了 3 次，如此算下來，其增長的速度是很可怕的。
\r 事實上，既然 f ( x ）的值取決於 f ( x 一 1 ) , f ( x 一 2 ）而 f ( x 一 l ）的值又取決於 f ( x 一 2 ) , f ( x 一 3 ) , 那麼，我們便可由 fto ）、 f ( 1 ）、 f ( 2 ）、 f ( 3 ）二算到 f ( x ) ，這樣的話，所花的時問就變成線性的了。
\r 這時候，程式中可放置一陣列，以儲存所得到的經驗，例如：
\r int f(x)
\r {
\r int dp[max-x];
\r int, I;
\r dp[ 0]=1;
\r dp[ 1]=1;
\r for(i=2; i \r {
\r dp[ i]=dp[ i-1]+dp[i-2];//不必再遞迴了
\r }
\r retum dp[x];
\r }
\r 此外，動態規畫還有很多極為有趣的應用，因而，我展開了我的研究。