北京大學acm國際大學生程序設計競賽課件(2)(存儲版)
【正文】 ? 討論 – 1014 動態(tài)規(guī)劃 ? 與遞歸程序相類，將對問題求解分解為對子問題求解；不同之處在于把子問題的解存起來，用空間換時間。 問題解答 ? 遞推公式 ? 令 表示長度為 N的漂亮籬笆中以高度為 i的木條開始，呈下降趨勢的籬笆的個數(shù)； ? 令 表示長度為 N的漂亮籬笆中以高度為 i的木條開始，呈上升趨勢的籬笆的個數(shù)； ? 則有公式： downiNT ,upiNT ,問題解答 d o w niNNupiN TT ??? 1,（ 1） （ 2） （ 3） 公式解釋 ?公式（ 1）：以 1開始的下降序列為 0個 ?公式（ 2）：可以由下降序列的個數(shù)推出上升序列的個數(shù)，如下圖： 公式解釋 i x1 x2 x3 x4 x5 x6 x7 N+1 Ni+1 i i i i i i i Ni+1 公式解釋 ?公式（ 3）：在以 j+1開始的下降序列中，第 2
教學課件相關推薦
鄂ICP備17016276號-1