【代码随想录】【算法训练营】【第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数组的二维实现、一维实现；物品、背包容积的先后遍历顺序、以及每个维度的大小遍历顺序。