動(dòng)態(tài)規(guī)劃理論基礎(chǔ)
動(dòng)規(guī)五部曲：
- 確定dp數(shù)組 下標(biāo)及dp[i] 的含義。
- 遞推公式：比如斐波那契數(shù)列 dp[i] = dp[i-1] + dp[i-2]。
- 初始化dp數(shù)組。
- 確定遍歷順序：從前到后or其他。
- 打印。
出現(xiàn)結(jié)果不正確：
- 打印dp日志和自己想的一樣：遞推公式、初始化或者遍歷順序出錯(cuò)。
- 打印dp日志和自己想的不一樣：代碼實(shí)現(xiàn)細(xì)節(jié)出現(xiàn)問題。
1049. 最后一塊石頭的重量 II
參考文檔：代碼隨想錄
題目：
有一堆石頭，每塊石頭的重量都是正整數(shù)。
每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：
如果 x == y，那么兩塊石頭都會(huì)被完全粉碎；
如果 x != y，那么重量為 x 的石頭將會(huì)完全粉碎，而重量為 y 的石頭新重量為 y-x。
最后，最多只會(huì)剩下一塊石頭。返回此石頭最小的可能重量。如果沒有石頭剩下，就返回 0。
- 示例：
輸入：[2,7,4,1,8,1]
輸出：1
解釋：
組合 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)化為 [2,7,1,8,1]，
組合 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)化為 [2,1,1,1]，
組合 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)化為 [1,1,1]，
組合 1 和 1，得到 0，所以數(shù)組轉(zhuǎn)化為 [1]，這就是最優(yōu)值。- 提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
分析：
剛開始解題出現(xiàn)了誤區(qū)，對(duì)stone從小到大的排列，偶數(shù)相鄰元素之間抵消成新的值，奇數(shù)最大和最小抵消形成新的值后轉(zhuǎn)為偶數(shù)的計(jì)算。一輪計(jì)算之后重復(fù)計(jì)算直到集合只剩一個(gè)元素。這個(gè)思路是重復(fù)的排列和相鄰的抵消。這就不屬于動(dòng)態(tài)規(guī)劃了，在動(dòng)態(tài)規(guī)劃中，將整個(gè)集合抽象為兩個(gè)集合，集合1是抵消的集合，集合2是被抵消的集合。集合1-集合2就是最后的結(jié)果，要想（集合1-集合2）最小，就要使兩個(gè)集合最接近，這就想到結(jié)合的和 sum/2，集合中是否存在子集和是最接近 sum/2 的，這個(gè)子集和就是所求的集合2。問題轉(zhuǎn)為13.分割子集和的問題。
代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-835196.html
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0, target = 0;
for(int i = 0; i < stones.size(); i++){
sum += stones[i];
}
target = sum/2;
vector<int> dp(target+1, 0);
for(int i = 0; i < stones.size(); i++){
for(int j = target; j >= stones[i]; j--){
dp[j] = max(dp[j], dp[j-stones[i]]+stones[i]);
}
}
sum = sum - dp[target] - dp[target];
return sum;
}
};
494. 目標(biāo)和
參考文檔：代碼隨想錄
分析：
正整數(shù)集合分成兩個(gè)正整數(shù)的集合，left與right，一個(gè)是正數(shù)，一個(gè)是即將加負(fù)號(hào)的負(fù)數(shù)。有l(wèi)eft-right=target; left + right = sum; 推出left = (target+sum)/2; 所有只要找到總集合中相加為left的方法個(gè)數(shù)就可以得到答案。問題轉(zhuǎn)為集合劃分為子集和，求實(shí)現(xiàn)子集和的方法數(shù)。所以是組合問題，遞推公式為dp[i] = dp[i] + dp[i-nums[i]]; dp[i]表示實(shí)現(xiàn)i原來的方法數(shù)，dp[i-nums[i]]表示不加nums[i]的最多方法數(shù)，這個(gè)集合加入nums[i]就會(huì)得到 i。初始化時(shí)候的dp[0]應(yīng)該設(shè)為1，這樣不會(huì)導(dǎo)致之后的相加一直是0，可以理解為集合和為0有一種方法就是全部都為0。其余位置的初始化為0。
代碼：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
//分析：兩個(gè)正數(shù)集合left、right，left-right=target，left+right=sum,left=(sum+target)/2
//接下來計(jì)算到left的集合的方法數(shù)，另一個(gè)就是right
//dp[i]含義：集合和為i的方法個(gè)數(shù)
//遞推公式：dp[i] = dp[i] + dp[i-nums[i]];
//初始化：dp[0] = 1,其余為0
//遍歷順序：0-1背包
int sum = 0, left = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
}
if((sum+target)%2 == 1) return 0;
if((sum + target) < 0) return 0;
left = (sum+target) / 2;
//初始化
vector<int> dp(left+1, 0);
dp[0] = 1;
for(int i = 0; i < nums.size(); i++){
for(int j = left; j >= nums[i]; j--){
dp[j] = dp[j] + dp[j-nums[i]];
}
}
return dp[left];
}
};
474.一和零
參考文檔：代碼隨想錄
分析：
dp[i][j]含義是i個(gè)0，j個(gè)1的集合中最大的字符串個(gè)數(shù)。
進(jìn)而遞推公式是dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1); 所以本題和0-1背包的滾動(dòng)數(shù)組是類似的，只不過在是否放入背包的條件中不僅有0的限制還有1的限制，這表明在背包的循環(huán)體中處理的背包由一維上升到了二維。
在遍歷順序上，必須先物品再背包，在物品的循環(huán)體中需要計(jì)算出該物品中0的個(gè)數(shù)和1的個(gè)數(shù)，在背包中，需要判斷該不該把這個(gè)物品放入容量為i個(gè)0，j個(gè)1的背包中。在背包的遍歷順序中，應(yīng)該和滾動(dòng)數(shù)組的行為保持一致，需要倒序。
在初始化中，有一點(diǎn)干擾到了我，我將0-1背包的二維初始化和這個(gè)背包的二維初始化聯(lián)系起來，所以思考怎么初始化行、初始化列，但是這個(gè)聯(lián)系就是錯(cuò)誤的，dp[i][j]的含義是i個(gè)0，j個(gè)1的背包可以容納的最多個(gè)數(shù)的字符串個(gè)數(shù)，所以dp數(shù)組中每個(gè)位置的初始化應(yīng)該由之后背包的遍歷中確定，剛開始的初始化和滾動(dòng)數(shù)組的初始化一直，全部設(shè)為0。文章來源：http://www.zghlxwxcb.cn/news/detail-835196.html
代碼：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
//題目分析為有兩個(gè)維度的背包，一個(gè)是m，另一個(gè)是n
//dp[i][j]：有i個(gè)0，j個(gè)1的集合的最大長(zhǎng)度。（?。。。?/span>
//遞推公式：dp[i][j] = max(dp[i][j], dp[i-zeroNum][j-oneNum]+1);
//初始化：全0
//遍歷順序：先物品再背包，因?yàn)橄任锲沸枰?jì)算出二進(jìn)制字符串中0和1的個(gè)數(shù)
int zeroNum = 0, oneNum = 0;
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for(int i = 0; i < strs.size(); i++){
zeroNum = 0, oneNum = 0;
for(char c : strs[i]){
if(c == '0') zeroNum++;
else oneNum++;
}
for(int j = m; j >= zeroNum; j--){
for(int k = n; k >= oneNum; k--){
dp[j][k] = max(dp[j][k], dp[j-zeroNum][k-oneNum]+1);
}
}
}
return dp[m][n];
}
};
到了這里，關(guān)于【Day43】代碼隨想錄之動(dòng)態(tài)規(guī)劃0-1背包_1049. 最后一塊石頭的重量 II_494. 目標(biāo)和_ 474.一和零的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
