建站
咨詢
售后
建站咨詢
新聞中心
大家好，我是前端西瓜哥，有三個(gè)月沒(méi)做算法題了，這次就來(lái)做一道動(dòng)態(tài)規(guī)劃中難度較低的題。
公司主營(yíng)業(yè)務(wù)：網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。成都創(chuàng)新互聯(lián)公司是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。成都創(chuàng)新互聯(lián)公司推出資興免費(fèi)做網(wǎng)站回饋大家。
題目
給你一個(gè)只包含正整數(shù)的非空數(shù)組 nums。請(qǐng)你判斷是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。
示例 1：
輸入：nums = [1,5,11,5]
輸出：true
解釋：數(shù)組可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
輸入：nums = [1,2,3,5]
輸出：false
解釋：數(shù)組不能分割成兩個(gè)元素和相等的子集。
題目來(lái)源：
https://leetcode.cn/problems/partition-equal-subset-sum。
題解
動(dòng)態(tài)規(guī)劃，它的模型需要符合 多階段決策最優(yōu)解模型，即要推導(dǎo)出最后的結(jié)果，它需要經(jīng)歷多個(gè)階段。
比如經(jīng)典的跳樓梯，假如你要跳到第 7 階梯的樓梯，你需要先知道跳到第 5 和第 6 階梯需要走的步數(shù)。
還比如 0-1 背包問(wèn)題，我們?cè)跊Q策是否要放入第 n 個(gè)物品，我們需要知道上一個(gè)決策完成后，書包的所有可能的重量。
這些都是 階段。我們讓多個(gè)選擇同時(shí)并行發(fā)生，產(chǎn)生一個(gè)個(gè)階段，并記下狀態(tài)，給下一個(gè)狀態(tài)使用。
我們回到正題。
題目意思是問(wèn)能否將數(shù)組拆分成兩個(gè)子數(shù)組，這兩個(gè)子數(shù)組的和相等。
其實(shí)這就等價(jià)于，數(shù)組元素中是否存在一個(gè)子數(shù)組，它的和為原數(shù)組的總和除以 2，這時(shí)它就變成了經(jīng)典 0-1 背包問(wèn)題，你需要決策每個(gè)階段是否放入特定的數(shù)組元素，直到剛好為總和除以 2。
0-1 背包問(wèn)題，有在書包有最大承重情況下，求放入物體的最大重量?；蚴翘嵘蕉S，求放入物體的最大價(jià)值。
這道題屬于前者。
先看完整的題解：
function canPartition(nums) {
const sum = nums.reduce((sum, curr) => sum + curr, 0);
if (sum % 2 === 1) return false;
const half = sum / 2;
if (nums[0] === half) return true;
const dp = new Array(nums.length);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(half + 1).fill(false);
}
dp[0][0] = true;
if (nums[0] <= half) {
dp[0][nums[0]] = true;
}
for (let i = 1; i < dp.length; i++) {
for (let j = 0; j < dp[i].length; j++) {
if (dp[i - 1][j] === true) {
dp[i][j] = true;
if (j + nums[i] < half) {
dp[i][j + nums[i]] = true;
} else if (j + nums[i] === half) {
return true;
}
}
}
}
return false;
};這里的要點(diǎn)是構(gòu)建一個(gè)二維布爾值數(shù)組 dp，用來(lái)保存每個(gè)階段的狀態(tài)，對(duì)于 dp[i][j]，i 表示決策第 i 個(gè)元素是否被放入，j 表示子數(shù)組總和。
所以 dp[i][j] 的意思就是在決策第 i 個(gè)元素的階段，是否存在一種可能，讓總和為 j。
因?yàn)楫?dāng)前階段需要靠上一個(gè)階段推導(dǎo)，所以我們需要初始化第一階段的狀態(tài)：
const dp = new Array(nums.length);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(half + 1).fill(false);
}
dp[0][0] = true;
if (nums[0] <= half) {
dp[0][nums[0]] = true;
}
然后推導(dǎo)下一個(gè)階段時(shí)，就遍歷上一階段的值，如果為 true，就基于它決策加入當(dāng)前元素和不加入當(dāng)前元素后得到的新的總和，在對(duì)應(yīng)的位置標(biāo)記為 true，直到和為目標(biāo)值。
for (let i = 1; i < dp.length; i++) {
for (let j = 0; j < dp[i].length; j++) {
if (dp[i - 1][j] === true) {
dp[i][j] = true;
if (j + nums[i] < half) {
dp[i][j + nums[i]] = true;
} else if (j + nums[i] === half) {
return true;
}
}
}
}其實(shí)還可以做內(nèi)存優(yōu)化，將二維數(shù)組轉(zhuǎn)換為一維數(shù)組，這需要用從后往前遍歷數(shù)組的技巧。
這里還用二維數(shù)組的解法，是因?yàn)樗€是比較經(jīng)典的，有普適性，適合用于講解。一些題目中，甚至能將優(yōu)化為幾個(gè)變量，比如跳樓梯。
結(jié)尾
動(dòng)態(tài)規(guī)劃，是有一定難度的算法題類型，也是面試大廠時(shí)比較常看到的題目，有掌握的必要性。
網(wǎng)站標(biāo)題：【動(dòng)態(tài)規(guī)劃】LeetCode題解：416-分割等和子集
轉(zhuǎn)載源于：http://www.5511xx.com/article/dhsgsho.html
