//------------------------------------------------------------

對于環形的動態規劃，

可以把數組下標復制一份然后進行動態規劃

//------------------------------------------------------------

在動態規劃的具體編程中，可能許多時候寫出了正確的狀態轉移方程，但編寫后的程序卻得不到正確解，這很有可能是因為動態規劃的循環的順逆序，或者循環的內外層出現了錯誤。

在這里忽略其他資料中的理論知識，而具體說動態規劃是如何實現的。

// 在這里的給出的全部代碼都沒有經過調試而直接寫出

// 如果出現錯誤，請指出

從01背包開始說起。

稍微掌握動態規劃的人都可以熟練地寫出如下代碼：

for(i=1;i<=n;i++)
  for(j=v;j>=c[i];j--)
    d[j]=max(d[j],d[j-c[i]]+w[i])；

一般的動態規劃都是先枚舉狀態再枚舉決策，可能初學者不明白以上的代碼是怎么回事，因為這是降維之后的狀態表示，降維之前的是：

d[i][j]=max(d[i-1][j],d[i-1][j-c[i]]+w[i])；

之所以可以降維是因為：觀察狀態轉移方程，第i次的決策只與第i-1次所記錄的狀態有關，于是想，能不能有一種方法只用一維數組，就可以在狀態轉移能夠正確進行？答案是肯定的，那就是第二層使用逆序循環。

NOIp 2006 金明的預算方案

先處理一下給出的物品，分成若干組，轉化為分組背包問題。

寫出分組背包的狀態轉移方程：

d[k][j]=max(d[k-1][j],d[k-1][j-c[k][i]]+w[k][i])；

對于分組背包，給出如下代碼：

for 所有組k
  for j=V to 0
    for 所有物品i屬于組k
      d[j]=max(d[j],d[j-c[k][i]]+w[k][i])；

// 《背包問題九講》中的代碼似乎有點錯誤

同樣，先觀察狀態轉移方程，還是只取決于第k-1組記錄的狀態，又要使每組中物品只選一件或者一件都不選。這樣就確定了分組背包只能是上面的循環次序，因為只有這樣在第k組決策的時候才能保證從第k-1組的狀態轉移而來；簡單地說就是，在第二層固定了前k組物品占用的空間，那么無論選擇哪一個i，最終這個狀態都只能被第k組的一個物品占用；試想如果像《背包問題九講》中那樣把第二層循環和第三層循環顛倒過來，那么就有可能第k層的狀態由第k層的狀態轉移而來，從而不能保證最多選擇一件物品。

Vijos GF

二維費用的背包。

狀態轉移方程直接給出如下：

d[i][j][k]=max(d[i-1][j][k],d[i-1][j-c1[i]][k-c2[i]]+w[i])；

同樣可以降到二維，因為是每個GF只能選擇一次（題目中好像沒有這么說，很久之前做的了，不太記得了，但是現實生活中的經驗告訴我們每個GF只能選擇一次），所以在循環枚舉j和k的時候要使用逆序。

Vijos 情敵

當然可以理解為和“金明的預算方案”一樣，是有依賴關系的背包問題，但是這道題卻在數據的規模上告訴我們用那種方法是不可行的。更好的做法是搜索和動態規劃結合，每次枚舉超級情敵在第一個月消滅、第二個月消滅、第三個月消滅（即不消滅），然后對其余情敵進行動態規劃。

省略搜索部分，而著重說說動態規劃。

狀態轉移方程：

d[i][j][k]=max(d[i-1][j][k],d[i-1][j-c1[i]][k],d[i-1][j][k-c2[i]])；

由于有可能某個超級情敵沒有被消滅，而在枚舉i的時候枚舉了這個超級情敵，如果在這時直接判斷后continue，可能造成d[i]層的空缺，以至于d[i+1]層的錯誤。所以在處理這樣可能出現某一層出現空缺的情況時，要把空缺的那一層全部從它的上一層把狀態繼承下來，以保證后來的狀態轉移的正確。

總結一下。

對于一道題目寫出狀態轉移方程之后，程序的實現有時候是顯而易見的，但有時候卻又需要思考一番。這時候還是需要立足于狀態轉移方程，另外還要考慮到題目中的一些限制條件，設計合適的循環順逆序和內外層。

//------------------------------------------------------------