動態規劃刷題筆記（一）
寫在前面
本專題是對半年來動態規劃刷題的一個簡單總結。老實説，這半年受困于課内知識和加權，沒怎麽動過算法題。但每次抽空的練習，也都讓我有了長足的進步，從普及-都難以完成的水平進步到了可以嘗試普及+/提高的樣子了。所以今天特地用寶貴的周四下午休息時間總結如下。
本次動態規劃整理筆記以問題分類入手，側重解決各種類別的入門及基礎題目，難度不會太大，大致為洛谷的普及-~普及/提高-難度。
數格子
在力扣上，這種類型又稱”矩陣“類型。這應該是最簡單的一類動態規劃題目，比斐波那契類型可能還要簡單一些，原因在於其難度上限有限，方法較爲固定。
leetcode 62.不同路徑
難度：中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例：
輸入：m = 3, n = 7
輸出：28
題解：
這個題目來源於我們小學的奧數題。到達一個格子的方式有兩種：
-
從左邊相鄰的格子到達
-
從上邊相鄰的格子到達
設坐標為(i,j)的格子到達路徑總數為dp[i][j]，則有狀態轉移方程：
狀態轉移方程得到了，我們只需確定初始條件即可開始遞推。而初始條件也是容易確定的。注意到對於上面的狀態轉移方程，i=0或j=0時數組會向下溢出，這説明dp[0][j]、dp[i][0]便是我們要的初始條件，即第一行及第一列的格子只有一種到達方式，那麽在開始遞推前將dp[0][j]、dp[i][0]全部賦值為1即可。
由此可得答案：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> grid(m,vector<int>(n,0));
for( int i=0 ; i<n ; i++ ) //第一行格子路徑數為1
grid[0][i]=1;
for( int i=0 ; i<m ; i++ ) //第一列同理
grid[i][0]=1;
for( int i=1 ; i<m ; i++ )
for( int j=1 ; j<n ; j++ )
grid[i][j]=grid[i-1][j]+grid[i][j-1];
return grid[m-1][n-1]; //終點路徑數即可
}
};
這道題是“數格子“問題的基礎類型，因爲它沒有任何限制條件。
本體和64. 最小路径和 - 力扣（LeetCode）類型相似，不再解釋。
洛谷 P1002 [NOIP2002普及組] 過河卒
難度：普及-
棋盘上\(A\)点有一个过河卒，需要走到目标\(B\)点。卒行走的规则：可以向下、或者向右。同时在棋盘上\(C\)点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，\(A\)点\((0,0)\)、\(B\)点\((n,m)\)，同样马的位置坐标是需要给出的。
现在要求你计算出卒从\(A\)点能够到达\(B\)点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
示例：
輸入：6 6 3 3
輸出：6
説明：\(1\leq n,m\leq 20,0\leq\)馬的坐標\(\leq 20\)
題解：
（小故事）我對於這個題的感情還是很深厚的。由於它是洛谷整個題庫的第三題，因此在二零年的時候就嘗試過，當然也是以失敗告終。去年這個時候陰間人誤以爲洛谷題目難度是順次排列的，還問過我這題，當時我還不會，然而前兩天并不很費力地就把它做出來了，還是很感慨的。
回到這個題目上，題目本身與象棋無關，仍然是數格子問題。甚至本題的狀態轉移方程都與”不同路徑“毫無區別。唯一不同的是，本體需要加上特判。
-
若在初始條件的判斷過程（即首行、首列）中遇到了馬及其控制點，則可以終止遍歷，未遍歷的點賦值為\(0\)（無法到達）
-
若是在遞推過程中遇到馬及其控制點，那麽原先兩條路徑只有一條可用了，直接讓
dp[i][j]等於不是控制點的路徑數即可。
具體實現方法上，先讓所有點路徑數為\(0\)，然後遍歷馬位置及其控制點，賦值為\(-1\)，即可按照上述思路進行遞推和特判。
標程不給了，重要代碼如下：
//控制點位置推移
char direc[8][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
//控制點-1
for( int i=0 ; i<8 ; i++ ){
int nx = hx+direc[i][0],ny = hy+direc[i][1];
if( nx>=0&&nx<=n&&ny>=0&&ny<=m ) //防止溢出
dp[nx][ny] = -1;
}
//遞推
for( int i=1 ; i<=n ; i++ )
for( int j=1 ; j<=m ; j++ ){
if( dp[i][j]==-1 ) //這點是控制點
continue;
if( dp[i-1][j]==-1&&dp[i][j-1]==-1 ) //相鄰點都是控制點
continue;
if( dp[i][j-1]==-1 )
dp[i][j] = dp[i-1][j];
else if( dp[i-1][j]==-1 )
dp[i][j] = dp[i][j-1];
else
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
本題和63. 不同路径 II - 力扣（LeetCode）題目類型相似，不再解釋。
這兩類體型，數據類型都是矩陣，除此之外還有三角形數據，如題目P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles - 洛谷、120. 三角形最小路径和 - 力扣（LeetCode）解體思路相似，不再贅述。
洛谷 P1434 [SHOI2002] 滑雪
難度：普及/提高-
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为\(24−17−16−1\)（从\(24\)开始，在\(1\)结束）。当然\(25－24－23－…－3－2－1\)更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 R 和列数 C。下面是 R 行，每行有 C 个数，代表高度(两个数字之间用 1 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
示例
輸入：
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9輸出： 25
説明：\(1\leq R,C\leq 100\)
題解：
這可能是我做出來的第一道省選題，但并不是利用動態規劃做出來的，爲了滿足我的虛榮心我決定把我原本的做法也放上來。
法一：BFS
看到題目我第一下想到的就是廣度優先搜索。遍歷滑雪場的每個點，以該點爲起點，遇到比它低的相鄰點則將它壓入棧，從棧頂取元素重複，一直到棧空爲止。棧的元素類型可以設爲數組，數組元素為：\(\{橫坐標，縱坐標，滑雪長度\}\)。算法核心代碼如下：
for( int i=0 ; i<m ; i++ )
for( int j=0 ; j<n ; j++ ){ //遍歷每個點
stack<vector<int>> st; //定義棧類型
st.push({i,j,1}); //初始入棧元素
while(!st.empty()){
vector<int> temp = st.top();st.pop(); //出棧
int nx = temp[0], ny = temp[1], len = temp[2];
if( len>ans ) //遇到更長路徑，更新答案
ans = len;
for( int k=0 ; k<4 ; k++ ){
int tx = nx+dire[k][0], ty = ny+dire[k][1];
if( tx>=0&&tx<m&&ty>=0&&ty<n&&grid[nx][ny]>grid[tx][ty] )
st.push({tx,ty,len+1}); //遇到更低點，入棧
}
}
}
淺淺算一下時間複雜度，最壞情況下對於每個起點，所有點都要遍歷一次，時間複雜度應爲\(O(R^2C^2)\)。最多計算\(10^8\)次，賭賭運氣也許行。
提交，果然一個點\(TLE\)。
法二：隊列+動態規劃
\(TLE\)是最難受的，它意味著如果你想提高成績，只能從頭做起，優化算法了。
不過恰好動態規劃正是一種”空間換時間“的利器，於是考慮用動態規劃優化算法。首先狀態轉移方程也是較爲明確的，即當前格的最長路徑應爲周圍四個格中比當前格低的格子長度最大值+1。初始條件也是比較確定的，沒有滑動時，每個格子的最長路徑都是1。
但是應當以何種方式（何種順序）去遞推呢？若逐行列遞推，可能會有狀態更新但未存儲的情況，如：
3 1 4
6 2 7
5 9 8
在這個地圖中，若逐行列遞推，則可得\(dp(3)=2,dp(1)=1,...\) \(,dp(9)=3\)，然而事實上\(dp(9)=5\)，從\(9\)出發是最長的一條。這是因爲最長的一條是從\(9\)到\(8\)延伸，但此時按照遞推順序，\(8\)還沒有進行狀態更新，在專業裏，這個貌似被稱爲無後效性。
因此，最正確的方法是從小到大進行遞推。建立一個隊列，海拔小的在前，海拔大的在後，依次出隊進行遞推，能夠保證遞推時途徑的節點狀態已更新。
核心代碼如下：
//構造隊列
queue<vector<int>> q;
int flag[105][105]={0}; //標記節點是否已在隊列中
for( int k=0 ; k<m*n ; k++ ){
int nmin = 10000000;
vector<int> temp(2,0); //隊列元素為記錄坐標的數組
for( int i=0 ; i<m ; i++ )
for( int j=0 ; j<n ; j++ ){
if( grid[i][j]<nmin&&flag[i][j]==0 ){
nmin = grid[i][j];
temp[0] = i;temp[1] = j;
}
}
q.push(temp); //入隊
flag[temp[0]][temp[1]] = 1; //更新標記
}
//動態規劃過程
while(!q.empty()){
int i = q.front()[0], j =q.front()[1];q.pop();
if( i-1>=0&&grid[i-1][j]<grid[i][j] )
dp[i][j] = max(dp[i][j],dp[i-1][j]+1);
if( j-1>=0&&grid[i][j-1]<grid[i][j] )
dp[i][j] = max(dp[i][j],dp[i][j-1]+1);
if( i+1<m&&grid[i+1][j]<grid[i][j] )
dp[i][j] = max(dp[i][j],dp[i+1][j]+1);
if( j+1<n&&grid[i][j+1]<grid[i][j] )
dp[i][j] = max(dp[i][j],dp[i][j+1]+1);
if( ans<dp[i][j] )
ans = dp[i][j];
}
這樣得到的答案可以在\(1s\)内解決。
類似的，我們可以使用優先隊列確定遞推順序，這比自己寫確定順序的代碼要快得多。
此外，還有記憶化搜索的方法，可以參考题解 P1434 【[SHOI2002]滑雪】 - Rainy7の灯塔不再贅述。
931. 下降路径最小和 - 力扣（LeetCode）是與此相似的題目，但是可以直接按行列遞推，所以難度大減。
leetcode 221.最大正方形
難度：中等
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
題解：
這是本專題的最後一題了，事實上和所謂的”數格子“已經大相徑庭了，難度也有所提升。
印象裏很久以前寫過類似的題，當然是使用暴力法，力扣官方也給出了這樣的解法（但貌似和bfs一樣會超時）。
本題的狀態轉移方程十分巧妙。若dp[i][j]表示包含(i,j)的最大正方形的邊長，則有：
即包含(i,j)的最大正方形的邊長為包含左上相鄰三點的最大正方形邊長的最小值加上自身的值。這是很巧妙的，你需要發現當前正方形邊長與左上三點的最小值有關。
初始條件也是確定的，遍歷首行、首列，若格為1則記dp為1，否則為0。
標程不再給出。
斐波那契類型
這應該是動態規劃最基礎的類型，我時常懷疑動態規劃就是爲了解決這些問題引入的。斐波那契數列我們都很熟悉，其狀態轉移方程爲：
\[f[n] = f[n-1]+f[n-2] \]可以采用遞歸的方式解決，但對於\(n\geq42\)的情況，時間就會超過\(1s\)，采用遞歸會使得所用時間較長。這是因爲每次遞歸都要從\(n\)遞歸到\(2\)才能返回，重複算了太多次，因此采用了這種”空間換時間“的方式。
解答此類問題，應著重關注原問題與”重叠子問題“的關係。
leetcode 746.使用最小花費爬樓梯
難度：簡單
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例1：
輸入：cost = [10,15,20]
輸出：15
示例2：
輸入：cost = [1,100,1,1,1,100,1,1,100,1]
輸出：6
輸入中加粗的是答案所走的路徑。
題解：
這個題確實挺簡單的。狀態轉移方程可以很明顯地得出：
\[dp[i] = min(dp[i-1],dp[i-2])+cost[i] \]初始條件應爲\(dp[0]=cost[0],dp[1]=cost[1]\)。從下標為\(2\)的臺階開始遞推即可。這和我們《離散數學（二）》的《高級計數技術》這一章有點像。
簡單題做這一個就行，本題主要作爲斐波那契類型的引入。
leetcode 198.打家劫舍
難度：中等
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
題解：
本體和最小花費爬樓梯其實基本一致，狀態轉移方程是比較明確的。若用\(dp[i]\)表示當前所偷到的最大值，則有：
\[dp[i] = max(dp[i-2]+num[i],dp[i-1]) \]即對於第\(i\)家，選擇偷或不偷，偷的話則不能偷第\(i-1\)家。
初始狀態可能略有些坑，因爲本題的狀態轉移看似只需要前一個狀態值，要隔一個數，因此需要\(dp[0]\)和\(dp[1]\)兩個狀態。注意
\[dp[0]=num[0],dp[1]=max(num[0],num[1]) \]\(dp[1]\)不是直接用\(num[1]\)賦值，可能存在”偷0不偷1的情況“。
據此可編寫代碼：
class Solution {
public:
int rob(vector<int>& nums) {
int len=nums.size();
if( len==1 )
return nums[0];
vector<int> dp(len,0);
dp[0]=nums[0];dp[1]=max(nums[0],nums[1]); //初始條件
for( int i=2 ; i<len ; i++ )
dp[i]=max(dp[i-2]+nums[i],dp[i-1]); //狀態轉移
return dp[len-1];
}
};
leetcode 740.刪除並獲得點數
難度：中等
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。説明：\(1\leq nums[i]\leq 10^4\)
題解：
在打家劫舍這個題目的基礎上，本題的難點則在於轉化爲我們熟悉的形式。本題中”刪除所有等于 nums[i] - 1 和 nums[i] + 1 的元素“可以理解爲刪除掉這一點數后，相鄰的點數就不能再取了。這與打家劫舍十分類似。可以建立這樣的數組\(dp\)：
大小爲數組中數字的最大值，每個點數\(i\)出現一次，則\(dp[i]+=1\)。然後按照打家劫舍的方式進行遞推，只是將狀態轉移方程改爲：
\[dp[i] = max(dp[i-2]+cost[i]*i,dp[i-1]) \]因爲點數不止一個。
據此可編寫代碼：
class Solution {
public:
int deleteAndEarn(vector<int>& nums) {
int credits=0,maxnum=0,len=nums.size();
for( int i=0 ; i<len ; i++ )
maxnum=max(maxnum,nums[i]);
vector<int> cost;cost.resize(maxnum+1,0);
for( int i=0 ; i<len ; i++ )
cost[nums[i]]++;
vector<int> ans;ans.resize(maxnum+1,0);
ans[0]=0;ans[1]=cost[1];
for( int i=2 ; i<=maxnum ; i++ )
ans[i]=max(ans[i-1],ans[i-2]+cost[i]*i);
return ans[maxnum];
}
};
這是本類型的最後一題。可以看到，斐波那契類型更像是動態規劃的引入，很少用\(OI\)題采用這一類型。
背包問題
也是動態規劃問題中最爲經典的一類。背包問題最常見的情景為：在有限的時間/空間内達到最優化的效果。這種效果可以是東西最多，也可能是價值最高。若談論到價值，則這個問題是有權的，較爲複雜。
背包問題也分多種，例如01背包、完全背包、分組背包等等。我們將逐個討論。
洛谷 P1060 [NOIP2006普及組] 開心的金明
P1060 [NOIP2006 普及组] 开心的金明 - 洛谷
難度：普及-
金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 \(N\) 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 \(N\) 元。于是，他把每件物品规定了一个重要度，分为 \(5\) 等：用整数 \(1-5\) 表示，第 \(5\) 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 \(N\) 元（可以等于 \(N\) 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第\(j\)件物品的价格为 \(v_j\)，重要度为 \(w_j\)，共选中了 \(k\) 件物品，编号依次为 \(j_1,j_2,…,j_k\)，则所求的总和为：
\(v_{j_1} \times w_{j_1}+v_{j_2} \times w_{j_2} …+v_{j_k} \times w_{j_k}\)。
请你帮助金明设计一个满足要求的购物单。
输入:
第一行，为 \(2\) 个正整数，用一个空格隔开：\(n,m\)（\(n<30000,m<25\)）其中 \(n\) 表示总钱数，\(m\) 为希望购买物品的个数。
从第 \(2\) 行到第 \(m+1\) 行，第 \(j\) 行给出了编号为 \(j-1\) 的物品的基本数据，每行有 \(2\) 个非负整数 \(v,p\)（其中 \(v\) 表示该物品的价格 \((v \le 10000)\)，\(p\) 表示该物品的重要度（\(1\le p\le5\)）。
输出格式
\(1\) 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（\(<100000000\)）。
输入
1000 5
800 2
400 5
300 5
400 3
200 2
输出
3900
題解：
物品只能購買一次，即只有取和不取兩種狀態，這很明顯是個01背包問題。
01背包問題的狀態轉移方程是基本確定的，即：對於每個容量，是否選取這個物品，若不選取，則仍為原值，否則更新爲這個物品占用后剩餘容量的最大價值加上這個物品的最大價值。用公式表述爲：
\[dp[j] = max(dp[j],dp[j-v[i]]+w[i]) \]對於01背包問題，應外層遍歷物品，内層遍歷容量。（套板子是這樣的）并且容量應倒搜，這是因爲每個物品只能取一次。
據此可編寫代碼：
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int v[26],w[26];
for( int i=1 ; i<=m ; i++ )
cin>>v[i]>>w[i];
int dp[30001]={0};
for( int i=1 ; i<=m ; i++ )
for( int j=n ; j>=v[i] ; j-- ){ //注意要倒搜
dp[j]=max(dp[j],dp[j-v[i]]+v[i]*w[i]);
}
cout<<dp[n];
return 0;
}
這是最爲基礎的一類01背包問題，幾乎完全套用模板。事實上，只要能將問題情景轉化01背包模型，剩下的就是套用板子的事情。類似或稍難一點的問題有：P1802 5 倍经验日 - 洛谷、P1049 [NOIP2001 普及组] 装箱问题 - 洛谷、P1048 [NOIP2005 普及组] 采药 - 洛谷
洛谷 P1507 NASA的食物計劃
難度：普及-
NASA（美国航空航天局）因为航天飞机的隔热瓦等其他安全技术问题一直大伤脑筋，因此在各方压力下终止了航天飞机的历史，但是此类事情会不会在以后发生，谁也无法保证。所以，在遇到这类航天问题时，也许只能让航天员出仓维修。但是过多的维修会消耗航天员大量的能量，因此 NASA 便想设计一种食品方案，使体积和承重有限的条件下多装载一些高卡路里的食物。
航天飞机的体积有限，当然如果载过重的物品，燃料会浪费很多钱，每件食品都有各自的体积、质量以及所含卡路里。在告诉你体积和质量的最大值的情况下，请输出能达到的食品方案所含卡路里的最大值，当然每个食品只能使用一次。
输入格式
第一行 \(2\) 个整数，分别代表体积最大值 \(h\) 和质量最大值 \(t\)。
第二行 \(1\) 个整数代表食品总数 \(n\)。
接下来 \(n\) 行每行 \(3\) 个数 体积 \(h_i\)，质量 \(t_i\)，所含卡路里 \(k_i\)。
输出格式
一个数，表示所能达到的最大卡路里（int 范围内）
输入
320 350
4
160 40 120
80 110 240
220 70 310
40 400 220
输出
550
对于 \(100\%\) 的数据，\(h,t,h_i,t_i \le 400\)，\(n \le 50\)，\(k_i \le 500\)。
題解：
這是個二維的01背包，與“開心的金明”不同，本題的“容量”包含兩個維度：體積和質量。因此需要將\(dp\)設置爲二維數組，大小分別爲體積最大值和質量最大值。然後利用狀態轉移方程
\[dp[j][p] = max(dp[j][k],dp[j-j[i]][p-t[i]]+k[i]) \]即可。
int mh, mt, n;
cin>>mh>>mt>>n;
int h[51], t[51], k[51];
for( int i=0 ; i<n ; i++ )
cin>>h[i]>>t[i]>>k[i];
int dp[401][401];
for( int i=0 ; i<n ; i++ ){
for( int j=mh ; j>=h[i] ; j-- ){
for( int p=mt ; p>=t[i] ; p-- ){
dp[j][p] = max(dp[j][p],dp[j-h[i]][p-t[i]]+k[i]);
}
}
}
ps：有點後悔，這題沒必要單獨解釋。
leetcode 518.零錢兌換 II
難度：中等
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例：
输入：amount = 5, coins = [1, 2, 5]
输出：4解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
題解：
這是一道完全背包問題。與01背包不同的是，在完全背包裏，物品的數量是不限的，只要滿足容量條件即可多次選取。根據01背包的經驗，無需改變内外循環，也無需改變狀態轉移方程，只需進行正搜即可。
源代碼：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int>dp(amount+1,0);
dp[0] = 1;
for( int i=0 ; i<n ; i++ ){
for( int j=coins[i] ; j<=amount ; j++ ) //正搜
dp[j] += dp[j-coins[i]];
}
return dp[amount];
}
};
類似的題目有：279. 完全平方数 - 力扣（LeetCode）、P1616 疯狂的采药 - 洛谷。可以看到，完全背包也不過是套板子。
洛谷 P1757 通天之分組背包
難度：普及-
自 \(01\) 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 \(01\) 背包，他的物品大致可分为 \(k\) 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入格式
两个数 \(m,n\)，表示一共有 \(n\) 件物品，总重量为 \(m\)。
接下来 \(n\) 行，每行 \(3\) 个数 \(a_i,b_i,c_i\)，表示物品的重量，利用价值，所属组数。
输出格式
一个数，最大的利用价值。
输入#1
45 3
10 10 1
10 5 1
50 400 2
输出#1
10
\(1 \leq m, n \leq 1000\)，\(1\leq k\leq 100\)，\(a_i, b_i, c_i\) 在 int 范围内。
題解：
如題目所給，這是一道分組背包問題。分組背包的難點主要有兩部分：
-
認清每個物品是那一組的
-
確保每組中只取了小於或等於一個物品
第一點並不難做到，只需在輸入過程中用一個數組記錄下分組情況即可：
for( int i=1 ; i<=n ; i++ ){
cin>>a[i]>>b[i]>>x;
temp = max(x,temp); //记录最大组数
c[x] ++;
group[x][c[x]] = i; //x组的第c[x]个的编号为i
}
第二點則需要從循環順序的方面來解決。在01背包和完全背包中，我們先遍歷物品，再遍歷容量，作用是用於判斷是否選取一個物品（選取多少個）。而在分組背包中我們要確定的是，在同一組中，在容量有限的情況下，選取一個“最佳”的物品。背包大小循環一遍才表示一個物品放進去，所以只需先遍歷容量，再遍歷物品即可。同時，爲防止本題一個物品重複取，應對容量進行倒搜。
for( int i=1 ; i<=temp ; i++ )
for( int k=m ; k>=0 ; k-- )
for( int j=1 ; j<=c[i] ; j++ )
if( k>=a[group[i][j]] )
dp[k] = max(dp[k],dp[k-a[group[i][j]]]+b[group[i][j]]);
核心代碼已給出，標程從略。
可以看到，對於背包問題的評級，洛谷給出的一般均爲普及-。這是因爲對於背包問題，往往是可以直接套用模板的。
動態規劃刷題筆記（一）到此結束。隨著練習的深入，後續會有狀態機、前綴和的題目分析，敬請期待。
2023.10.14
标签：背包,nums,筆記,狀態,刷題,規劃,int,問題,dp From： https://www.cnblogs.com/sisyphus-616/p/17776286.html