淄博 做网站,学雷锋做美德少年网站,直播app,家装设计需要学什么软件关于此题我的往期文章#xff1a;
LeetCode 416.分割等和子集#xff08;动态规划【0-1背包问题】采用一维数组dp:滚动数组#xff09;_呵呵哒(#xffe3;▽#xffe3;)的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133212716看本期文章时…关于此题我的往期文章
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?spm1001.2014.3001.5501
leetCode 198.打家劫舍 动态规划入门:从记忆化搜索到递推-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134179583?spm1001.2014.3001.5501 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等 最优的子结构性质这是解决动态规划问题的关键。最优解可以从其子问题的最优解构造出来。如何将问题分解成子问题
1递归 class Solution {
public:// 递归 超出时间限制bool canPartition(vectorint nums) {int nnums.size(),sum0;for(const int x:nums) sumx;if(sum % 2 1) return false;int left sum/2; // 目标和functionint(int,int) dfs[](int i,int c) - int {if(i0) {if(c0) return 0;else return INT_MIN;}if(cnums[i]) return 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 ans0?false:true;}
};
2递归搜索 保存计算结果 记忆化搜索
在递归树中有许多子问题被多次计算。为了避免重复的计算可以将每个子问题的答案存在一个数组中进行记忆化如果下次还要计算这个问题的值直接从数组中取出返回即可这样能保证每个子问题最多只被计算一次。
class Solution {
public:// 记忆化搜索bool canPartition(vectorint nums) {int nnums.size(),sum0;for(const int x:nums) sumx;if(sum % 2 1) return false; // 如果 sum 为奇数直接返回 falseint left sum/2,memo[n1][left1]; memset(memo,-1,sizeof(memo));functionint(int,int) dfs[](int i,int c) - int {if(i0) {if(c0) return 0;else return INT_MIN;}int res memo[i][c];if(res ! -1) return res;if(cnums[i]) return resdfs(i-1,c);return resmax(dfs(i-1,c),dfs(i-1,c-nums[i])nums[i]);}; int ans dfs(n-1,left); return ans0?false:true;}
};
31:1 翻译成递推 初始化根据递归的边界来初始化
if(i0) {if(c0) return 0;else return INT_MIN;
}
f 数组初始化为 INT_MINdfs(-1,0) 0 翻译f[0][0]0
返回最终结果根据 dfs(n-1,left) 翻译 f[n][left]
class Solution {
public: // 递推bool canPartition(vectorint nums) {int nnums.size(),sum0;for(const int x:nums) sumx;if(sum % 2 1) return false; // 如果 sum 为奇数直接返回 falseint left sum/2,f[n1][left1];memset(f,128,sizeof(f)); // 无穷小f[0][0]0;for(int i0;in;i) {for(int c0;cleft;c) {if(c nums[i]) f[i1][c] f[i][c];else f[i1][c] max(f[i][c],f[i][c-nums[i]]nums[i]);}}int ansf[n][left]; return ans0 ? false:true;}
};
4空间优化两个数组滚动数组
f[(i1)%2][c] max(f[i%2][c],f[i%2][c-nums[i]]nums[i]);
class Solution {
public:// 递推 优化空间二维bool canPartition(vectorint nums) {int nnums.size(),sum0;for(const int x:nums) sumx;if(sum % 2 1) return false; // 如果 sum 为奇数直接返回 falseint left sum/2,f[2][left1];memset(f,128,sizeof(f)); // 无穷小f[0][0]0;for(int i0;in;i) {for(int c0;cleft;c) {if(c nums[i]) f[(i1)%2][c] f[i%2][c];else f[(i1)%2][c] max(f[i%2][c],f[i%2][c-nums[i]]nums[i]);}}int ansf[n%2][left]; return ans0 ? false:true;}
};
5空间优化一个数组
f[i1][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(vectorint nums) {int nnums.size(),sum0;for(const int x:nums) sumx;if(sum % 2 1) return false; // 如果 sum 为奇数直接返回 falseint left sum/2,f[left1];memset(f,128,sizeof(f)); // 无穷小f[0]0;for(int i0;in;i) {for(int cleft;cnums[i];c--) {f[c] max(f[c],f[c-nums[i]]nums[i]);}}int ansf[left]; return ans0 ? false:true;}
};可以改成
for(const int x:nums) {for(int cleft;cx;c--) {f[c] max(f[c],f[c-x]x);}
}
参考和推荐文章
利用memset 赋值无穷大和无穷小_如何使用memset函数初始化数组的值为无穷小_Prudento的博客-CSDN博客https://blog.csdn.net/Prudento/article/details/123534212416. 分割等和子集 - 力扣LeetCodehttps://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
