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

題目

給你一個只包含正整數(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)解模型，即要推導(dǎo)出最后的結(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。

因為當前階段需要靠上一個階段推導(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)下一個階段時，就遍歷上一階段的值，如果為 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ī)劃，是有一定難度的算法題類型，也是面試大廠時比較常看到的題目，有掌握的必要性。