大家好，我是前端西瓜哥，有三個(gè)月沒做算法題了，這次就來做一道動(dòng)態(tài)規(guī)劃中難度較低的題。

題目

給你一個(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è)元素和相等的子集。

題目來源：

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 背包問題，我們?cè)跊Q策是否要放入第 n 個(gè)物品，我們需要知道上一個(gè)決策完成后，書包的所有可能的重量。

這些都是 階段。我們讓多個(gè)選擇同時(shí)并行發(fā)生，產(chǎn)生一個(gè)個(gè)階段，并記下狀態(tài)，給下一個(gè)狀態(tài)使用。

我們回到正題。

題目意思是問能否將數(shù)組拆分成兩個(gè)子數(shù)組，這兩個(gè)子數(shù)組的和相等。

其實(shí)這就等價(jià)于，數(shù)組元素中是否存在一個(gè)子數(shù)組，它的和為原數(shù)組的總和除以 2，這時(shí)它就變成了經(jīng)典 0-1 背包問題，你需要決策每個(gè)階段是否放入特定的數(shù)組元素，直到剛好為總和除以 2。

0-1 背包問題，有在書包有最大承重情況下，求放入物體的最大重量。或是提升到二維，求放入物體的最大價(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，用來保存每個(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í)比較常看到的題目，有掌握的必要性。