動態規劃程序設計是對解最優化問題的一種途徑、一種方法，而不是一種特殊算法。不象搜索或數值計算那樣，具有一個標准的數學表達式和明確清晰的解題方法。動態規劃程序設計往往是針對一種最優化問題，由於各種問題的性質不同，確定最優解的條件也互不相同，因而動態規劃的設計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態規劃算法，可以解決各類最優化問題。因此讀者在學習時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態規劃算法進行分析、討論，逐漸學會並掌握這一設計方法。
所以dp算法的難點在於找狀態轉移方程。在poj做了一些動態規劃的題目，在這裡做個總結。
1、poj 1160
a 題目描述：
在v個村莊(村莊呈直線分布)設置p個郵局，使各個村莊到郵局的 總距離最短。
b 解題方案：
cost[v][p] 代表在v個村莊建立p個郵局的最短距離
dis[v][v] ；dis[i][j] 表示在第i個村莊和第j個村莊之間建立一個郵局，顯然，這個郵局應該建在i和j的中間。
c 狀態轉移方程：
cost[v][p] = cost[i][p-1] + dis[i+1][v] // p<=i<=v;
2、poj 1260
a 問題描述：
有c個種類的珠寶，每個種類的珠寶有需要購買的個數n和相應的價值p，需要購買某一種需要花費(n+10)*p; 購買時，低質量的珠寶可以用高質量的珠寶代替；為了最終花費的錢最少。
b 解題方案：
dp[c];dp[i]表示到第i中珠寶時花費的最少錢
num[c];num[i]表示從0到i之間質量的珠寶的所有數目
c 狀態轉移方程：
dp[i] = (num[i] + 10)*p[i]
dp[i] = min(dp[i],dp[j]+(num[i] - num[j] + 10)*p[i]) // 0<=j<i
3、poj 1276
a 問題描述：
有n中錢幣，每種有ai張，價值di；要求湊出m價值，求湊出的最接近m的值。
b 解決方法：
這是個多重背包問題，可以將重復價值的紙幣加起來，或者直接當成一個個體。這樣就變成01背包了。
c 狀態轉移方程：
for (i = 1; i<=count; i++) //count為有多少張錢幣，v[i]對應第i張錢幣的價值
for (k = m; k>=v[i]; k--) // m 為最終要拼出的價值
opt[k] = opt[k] | opt[k - v[i]]; //如果能拼出k，則opt[k]=1;
4、poj 1745
a 問題描述
給出一列數，可以在相鄰兩個數之間執行相加或者相減的操作，得出的所有結果中是否能被k整除。
b 解決方法
C[10001][101]; C[i][j]表示i個數字的運算結果sum, sum % k = j，若存在則為1，否則為0
c 狀態轉移方程
C[i][j] = C[i-1][(j-a[i])%k] | c[i-1][(j+a[i])%k]; //這裡需要防止 j-a[i] 和 j+a[i]為負數，所以還需做一些操作,為了簡便，這裡就不寫了
5、poj 1837
a 問題描述
天平平衡問題，有G砝碼，每個砝碼重量為g[i],需要將這n個砝碼掛在天平C個刻度上(c[i]表示刻度達標),要求天平最終要平衡。天平左邊的刻度用負數表示，右邊的刻度用正數表示。求平衡的方法有幾種。
b 解決方法
因為有負數存在，所以需要做偏移，最大偏移量為 ：M = 砝碼的最大重量*最大尺度*砝碼的最大個數。
w[i][j] //表示掛上第i個砝碼後，力矩為j的幾種方法
c 狀態轉移
for(i=1;i<=G;i++) //G個砝碼
for(j=1;j<=C;j++)//C個刻度
for(k=0;k<7501;k++) //力矩
{
w[i][k+g[i]*c[j]] += w[i-1][k]; //將第i個砝碼掛在第j個刻度上，力矩的變化
}
cout<<w[G][3500]<<endl;
