【代码随想录】【算法训练营】【第41天】 [416]分割等和子集

前言

思路及算法思维，指路 代码随想录。
题目来自 LeetCode。

day 40，休息，休息一下~
day 41，艰难的周一~

题目详情

[416] 分割等和子集

题目描述

416 分割等和子集

解题思路

前提：是否可以将数组分为和相等的两个子集，每个元素只能使用一次
思路：动态规划，0-1背包问题
重点：0-1背包问题的二维数组dp[i][j]的含义与实现；一维数组dp[j]的实现，尤其是遍历顺序的区别。

代码实现

C语言

二维数组dp[i][j]

// 0-1背包问题, 二维数组dp[i][j]: 从下标[0, i]中选取元素，限制在大小为j中的最大元素和
// dp[i][j] = max((dp[i-1][j-nums[i]] + nums[i]), dp[i-1][j])
int sumFun(int *nums, int numsSize)
{int sumTmp = 0;for (int i = 0; i < numsSize; i++) {sumTmp += nums[i];}return sumTmp;
}int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}bool canPartition(int* nums, int numsSize) {int sum = sumFun(nums, numsSize);if (sum % 2 == 1) {return false;}int target = sum / 2;int dp[numsSize][target + 1];// 初始化dp数组for (int j = 0; j <= target; j++) {if (j < nums[0]) {dp[0][j] = 0;} else {dp[0][j] = nums[0];}}// 从前向后遍历for (int i = 1; i < numsSize; i++) {for (int j = 0; j <= target; j++) {if (j < nums[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = maxFun((dp[i - 1][j - nums[i]] + nums[i]), dp[i - 1][j]);}}}if (dp[numsSize - 1][target] == target) {return true;}return false;
}

一维数组dp[j]

由于每个元素只能使用一次，所以对于内层遍历的元素和，需要从大到小遍历，即dp[j]的赋值不会引起dp[j-1]的数值变化，即从小到大遍历，会使元素i使用多次。

// 0-1背包问题, 一维数组dp[j]: 从下标[0, i]中选取元素，限制在大小为j中的最大元素和
// dp[j] = max((dp[j-nums[i]] + nums[i]), dp[j])
int sumFun(int *nums, int numsSize)
{int sumTmp = 0;for (int i = 0; i < numsSize; i++) {sumTmp += nums[i];}return sumTmp;
}int maxFun(int p1, int p2)
{return p1 > p2 ? p1 : p2;
}bool canPartition(int* nums, int numsSize) {int sum = sumFun(nums, numsSize);if (sum % 2 == 1) {return false;}int target = sum / 2;int dp[target + 1];// 初始化dp数组for (int i = 0; i < target + 1; i++) {dp[i] = 0;}// 从前向后遍历元素，从后向前遍历元素和for (int i = 0; i < numsSize; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = maxFun((dp[j - nums[i]] + nums[i]), dp[j]);}}if (dp[target] == target) {return true;}return false;
}

今日收获

1. 0-1背包问题：dp数组的含义、初始化、递推公式；dp数组的二维实现、一维实现；物品、背包容积的先后遍历顺序、以及每个维度的大小遍历顺序。