689. 三个无重叠子数组的最大和

413. 等差数列划分

446. 等差数列划分 II - 子序列

368. 最大整除子集

416. 分割等和子集

思路

转换成完全背包问题，利用动态规划来做

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {boolean}
  4.  */
  5. var canPartition = function(nums) {
  6.   // 先求和
  7.   let sum = nums.reduce((total, cur) => total + cur, 0);
  8.   // 如果为奇数直接返回
  9.   if (sum % 2) return false;
  10.   // 得到目标值
  11.   let target = sum / 2, len = nums.length;
  13.   // 初始化dp数组的值
  14.   let dp = Array(len).fill(0).map(item => Array(target+1).fill(false))
  15.   // 第一排只能填满自己
  16.   dp[0][nums[0]] = true;
  18.   for(let i = 1; i < nums.length; i ++) {
  19.     for(let j = 0; j <= target; j ++) {
  20.       // 先把上一排的抄下来再做处理
  21.       dp[i][j] = dp[i-1][j];
  22.       // 如果恰巧为当前值，那么可以填满自己
  23.       if (nums[i] === j) {
  24.         dp[i][j] = true;
  25.         continue;
  26.       }
  27.       // 如果小于当前值，看上一排的位置中能满足不
  28.       if (nums[i] < j) {
  29.         dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]
  30.       }
  31.     }
  32.   }
  33.   return dp[len-1][target];
  34. };

复杂度分析

时间复杂度 子数组、子序列中的动态规划 - 图1#card=math&code=O%28N%20%2A%20sum%29)
空间复杂度 子数组、子序列中的动态规划 - 图2#card=math&code=O%28N%20%2A%20sum%29)

279. 完全平方数