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