leetCode 416.分割等和子集 + 01背包 + 动态规划 + 记忆化搜索 + 递推 + 空间优化

关于此题我的往期文章：

LeetCode 416.分割等和子集（动态规划【0-1背包问题】采用一维数组dp:滚动数组）_呵呵哒(￣▽￣)"的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133212716看本期文章时，可以先回顾一下动态规划入门知识和完全背包理论和实战： 

0-1背包 完全背包 + 至多/恰好/至少 + 空间优化 + 常见变形题（实战力扣题）-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134210521?spm=1001.2014.3001.5501

leetCode 198.打家劫舍 动态规划入门:从记忆化搜索到递推-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134179583?spm=1001.2014.3001.5501 

---

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

---

最优的子结构性质，这是解决动态规划问题的关键。最优解可以从其子问题的最优解构造出来。如何将问题分解成子问题？

（1）递归

• 

class Solution {
public:
    // 递归 超出时间限制！
    bool canPartition(vector<int>& nums) {
        int n=nums.size(),sum=0;
        for(const int& x:nums) sum+=x;
        if(sum % 2 == 1) return false;
        int left = sum/2; // 目标和
        function<int(int,int)> dfs=[&](int i,int c) -> int {
            if(i<0) {
                if(c==0) return 0;
                else return INT_MIN;
            }
            if(creturn dfs(i-1,c);
            return max(dfs(i-1,c),dfs(i-1,c-nums[i])+nums[i]);
        };  
        int ans = dfs(n-1,left); 
        return ans<0?false:true;
    }
};

（2）递归搜索 + 保存计算结果 = 记忆化搜索

• 在递归树中，有许多子问题被多次计算。为了避免重复的计算，可以将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次。

class Solution {
public:
    // 记忆化搜索
    bool canPartition(vector<int>& nums) {
        int n=nums.size(),sum=0;
        for(const int& x:nums) sum+=x;
        if(sum % 2 == 1) return false; // 如果 sum 为奇数，直接返回 false
        int left = sum/2,memo[n+1][left+1]; 
        memset(memo,-1,sizeof(memo));
        function<int(int,int)> dfs=[&](int i,int c) -> int {
            if(i<0) {
                if(c==0) return 0;
                else return INT_MIN;
            }
            int &res = memo[i][c];
            if(res != -1) return res;
            if(creturn res=dfs(i-1,c);
            return res=max(dfs(i-1,c),dfs(i-1,c-nums[i])+nums[i]);
        };  
        int ans = dfs(n-1,left); 
        return ans<0?false:true;
    }
};

（3）1:1 翻译成递推

• 
• 
• 

初始化：根据递归的边界来初始化

if(i<0) {
    if(c==0) return 0;
    else return INT_MIN;
}

• f 数组初始化为 INT_MIN
• dfs(-1,0) = 0 翻译，f[0][0]=0

返回最终结果：根据 dfs(n-1,left) 翻译， f[n][left] 

class Solution {
public: 
   // 递推
    bool canPartition(vector<int>& nums) {
        int n=nums.size(),sum=0;
        for(const int& x:nums) sum+=x;
        if(sum % 2 == 1) return false; // 如果 sum 为奇数，直接返回 false
        int left = sum/2,f[n+1][left+1];
        memset(f,128,sizeof(f)); // 无穷小
        f[0][0]=0;
        for(int i=0;i
            for(int c=0;c<=left;c++) {
                if(c < nums[i]) f[i+1][c] = f[i][c];
                else f[i+1][c] = max(f[i][c],f[i][c-nums[i]]+nums[i]);
            }
        }
        int ans=f[n][left]; 
        return ans<0 ? false:true;
    }
};

（4）空间优化：两个数组（滚动数组）

• f[(i+1)%2][c] = max(f[i%2][c],f[i%2][c-nums[i]]+nums[i]);

class Solution {
public:
    // 递推 + 优化空间（二维）
    bool canPartition(vector<int>& nums) {
        int n=nums.size(),sum=0;
        for(const int& x:nums) sum+=x;
        if(sum % 2 == 1) return false; // 如果 sum 为奇数，直接返回 false
        int left = sum/2,f[2][left+1];
        memset(f,128,sizeof(f)); // 无穷小
        f[0][0]=0;
        for(int i=0;i
            for(int c=0;c<=left;c++) {
                if(c < nums[i]) f[(i+1)%2][c] = f[i%2][c];
                else f[(i+1)%2][c] = max(f[i%2][c],f[i%2][c-nums[i]]+nums[i]);
            }
        }
        int ans=f[n%2][left]; 
        return ans<0 ? false:true;
    }
};

（5）空间优化：一个数组

• f[i+1][c] = max(f[i][c]),f[i][c-nums[i]+nums[i]);
• f[c] = max(f[c],f[c-nums[i]]+nums[i]);

class Solution {
public:
    // 递推 + 优化空间（一维）
    bool canPartition(vector<int>& nums) {
        int n=nums.size(),sum=0;
        for(const int& x:nums) sum+=x;
        if(sum % 2 == 1) return false; // 如果 sum 为奇数，直接返回 false
        int left = sum/2,f[left+1];
        memset(f,128,sizeof(f)); // 无穷小
        f[0]=0;
        for(int i=0;i
            for(int c=left;c>=nums[i];c--) {
               f[c] = max(f[c],f[c-nums[i]]+nums[i]);
            }
        }
        int ans=f[left]; 
        return ans<0 ? false:true;
    }
};
 
 
可以改成
for(const int& x:nums) {
    for(int c=left;c>=x;c--) {
        f[c] = max(f[c],f[c-x]+x);
    }
}

参考和推荐文章：

利用memset 赋值无穷大和无穷小_如何使用memset函数初始化数组的值为无穷小_Prudento的博客-CSDN博客https://blog.csdn.net/Prudento/article/details/123534212416. 分割等和子集 - 力扣（LeetCode）https://leetcode.cn/problems/partition-equal-subset-sum/solutions/442412/shou-hua-tu-jie-fen-ge-deng-he-zi-ji-dfshui-su-si-/

常用技巧： 

memset(a,127,sizeof(a));
即得到无穷大。
memset(a,128,sizeof(a));
即得到无穷小，与上述的值互为相反数。
memset(a,60,sizeof(a));
即近似为第一个式子的数值的一半。
memset(a,0,sizeof(a));赋值0
memset(a,-1,sizeof(a));赋值-1
上述例子对于a数组为int或long long时，成立。
 
memset( , 0x3f , sizeof );
特意去试了下，发现 0x3f3f3f3f 真的是个非常精巧的常量
 
来自这篇博客：https://blog.csdn.net/Prudento/article/details/123534212