http://acm.sgu.ru/problem.php?contest=0&problem=222
這是入門題，數(shù)據(jù)較大，需要記憶化搜索

http://acm.pku.edu.cn/JudgeOnline/problem?id=1321
上題的提高版，不過(guò)數(shù)據(jù)超小，爆搜都能過(guò)

http://acm.sgu.ru/problem.php?contest=0&problem=223
先要預(yù)處理出一行中的全部可行狀態(tài)~
然后DP的時(shí)候巧妙的運(yùn)用位運(yùn)算進(jìn)行狀態(tài)的判斷和轉(zhuǎn)移
狀態(tài)dp中位運(yùn)算的巧妙運(yùn)用會(huì)大幅度提高程序的效率和帥氣程度

http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
非常經(jīng)典的狀態(tài)DP，由于攻擊范圍是兩格，所以要保持兩個(gè)狀態(tài)，有人用三進(jìn)制壓縮，我覺(jué)得太煩了(不能使用飄逸的位運(yùn)算）
但是[101][2^10][2^10]得狀態(tài)太大，考慮到2^10中有很多情況是不可到達(dá)的
計(jì)算下當(dāng)m=10的時(shí)候最多60個(gè)合法狀態(tài)，所以我開了[101][60][60]的數(shù)組記憶化DP過(guò)了

http://acm.hdu.edu.cn/showproblem.php?pid=2640
teddy大牛的題目，和上題差不多，不過(guò)不能重疊放，所以處理比上題煩很多
同樣2^8里有很多不可到達(dá)的情況，最多之有13種
所以我開[101][13][13]的數(shù)組15ms就過(guò)了，哈哈
這就好像是兩次狀態(tài)壓縮
最近的DP題目感覺(jué)到把很多不可到達(dá)的狀態(tài)壓縮掉效率會(huì)提高超多~也可能讓程序從TLE MLE變成AC~

http://acm.pku.edu.cn/JudgeOnline/problem?id=2411
http://acm.hdu.edu.cn/showproblem.php?pid=1400
這道其實(shí)很簡(jiǎn)單，先預(yù)處理出當(dāng)前狀態(tài)s1到下一狀態(tài)的可能值s2，hash[1<<m,1<<m]記錄，m為較小值
dp[0][(1<<m)-1] = 1
然后經(jīng)過(guò)n*(1<<m)*(1<<m)的循環(huán)得出結(jié)果dp[n][(1<<m)-1]

http://acm.sgu.ru/problem.php?contest=0&problem=223
兩種磚塊，除了預(yù)處理的時(shí)候狀態(tài)多點(diǎn)，有7種分支，其他的都和上一題一樣
(主意一個(gè)狀態(tài)到另一個(gè)狀態(tài)可能會(huì)有多種情況，hash的時(shí)候要用++而不是true false)

http://acm.hdu.edu.cn/showproblem.php?pid=2280
要求用最少的1鋪滿所有的空格，其中3是沒(méi)用的(可以用兩個(gè)5代替)，化簡(jiǎn)之后使用的方塊和上一題一樣，一樣的預(yù)處理后
dp求出最少的1

http://acm.pku.edu.cn/JudgeOnline/problem?id=1038
http://acm.hdu.edu.cn/showproblem.php?pid=2696
http://acm.hdu.edu.cn/showproblem.php?pid=2442
http://acm.hdu.edu.cn/showproblem.php?pid=1755
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=1668
http://acm.hdu.edu.cn/showproblem.php?pid=2518
http://acm.hdu.edu.cn/showproblem.php?pid=1666
http://acm.hdu.edu.cn/showproblem.php?pid=1820
http://acm.hdu.edu.cn/showproblem.php?pid=2315