一些題目：
背包問(wèn)題. (poj1837,poj1276)
型如下表的簡(jiǎn)單DP(可參考lrj的書(shū) page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長(zhǎng)公共子序列)
(poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優(yōu)二分檢索樹(shù)問(wèn)題)
較為復(fù)雜的動(dòng)態(tài)規(guī)劃(如動(dòng)態(tài)規(guī)劃解特別的施行商問(wèn)題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態(tài)的動(dòng)態(tài)規(guī)劃. (POJ3254,poj2411,poj1185)
樹(shù)型動(dòng)態(tài)規(guī)劃(poj2057,poj1947,poj2486,poj3140)
背包九講 http://www.concretevitamin.com.cn/informatics/Pack/Index.html
posted on 2009-03-18 19:53
爬 閱讀(1534)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
Dynamic programming