小说网站开发技术实现,增城住房和建设局网站,门户网站建设面临的困难,深圳全网推广平台关于本题我的往期文章#xff1a;
LeetCode 494.目标和 #xff08;动态规划 性能优化#xff09;二维数组 压缩成 一维数组_呵呵哒(#xffe3;▽#xffe3;)的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133253822 给你一个非负整数数组 nums…关于本题我的往期文章
LeetCode 494.目标和 动态规划 性能优化二维数组 压缩成 一维数组_呵呵哒(▽)的博客-CSDN博客https://heheda.blog.csdn.net/article/details/133253822 给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式
例如nums [2, 1] 可以在 2 之前添加 在 1 之前添加 - 然后串联起来得到表达式 2-1 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。 1递归
class Solution {
public:// 递归int findTargetSumWays(vectorint nums, int target) {int sum0,nnums.size();for(const int x:nums) sumx;if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案int addTarget (sum target) / 2;functionint(int,int) dfs [](int i,int c) - int {if(i0) return c0 ? 1 : 0;// 边界条件由于要求是恰好组成。恰好情况当c0的时候才能返回1表示这是一个合法的方案if(c-nums[i]0) return dfs(i-1,c);return dfs(i-1,c) dfs(i-1,c-nums[i]);};return dfs(n-1,addTarget);}
};
2递归搜索 保存计算结果 记忆化搜索
class Solution {
public:// 记忆化搜索int findTargetSumWays(vectorint nums, int target) {int sum0,nnums.size();for(const int x:nums) sumx;if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案int addTarget (sum target) / 2;vectorvectorint memo(n1,vectorint(addTarget1,-1));functionint(int,int) dfs [](int i,int c) - int {if(i0) return c0 ? 1 : 0;int res memo[i][c];if(res ! -1) return res;if(c-nums[i]0) return resdfs(i-1,c);return resdfs(i-1,c) dfs(i-1,c-nums[i]);};return dfs(n-1,addTarget);}
};
31:1 翻译成递推
dfs(i,c) dfs(i-1,c) dfs(i-1,c-w[i])f[i][c] f[i-1][c] f[i-1][c-w[i]]f[i1][c] f[i][c] f[i][c-w[i]]
初始化根据 if(i0) return c0 ? 1 : 0;
f 数组初始化为 0dfs(-1,0) 1 翻译f[0][0]1
返回最终结果根据 dfs(n-1,addTarget) 翻译 f[n][addTarget]
class Solution {
public:// 递推式int findTargetSumWays(vectorint nums, int target) {int sum0,nnums.size();for(const int x:nums) sumx;if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案int addTarget (sum target) / 2;vectorvectorint f(n1,vectorint(addTarget1,0));f[0][0]1;for(int i0;in;i) {for(int c0;caddTarget;c) {if(c-nums[i]0) f[i1][c]f[i][c];else f[i1][c]f[i][c] f[i][c-nums[i]];}}return f[n][addTarget];}
}; 优化空间
方式一二维数组优化
f[(i1)%2][c]f[i%2][c] f[i%2][c-nums[i]];
class Solution {
public:// 递推式 优化空间int findTargetSumWays(vectorint nums, int target) {int sum0,nnums.size();for(const int x:nums) sumx;if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案int addTarget (sum target) / 2;vectorvectorint f(2,vectorint(addTarget1,0));f[0][0]1;for(int i0;in;i) {for(int c0;caddTarget;c) {if(c-nums[i]0) f[(i1)%2][c]f[i%2][c];else f[(i1)%2][c]f[i%2][c] f[i%2][c-nums[i]];}}return f[n%2][addTarget];}
};
方式二一维数组优化
f[i1][c]f[i][c] f[i][c-nums[i]];f[c]f[c] f[c-nums[i]];
class Solution {
public:// 递推式 优化空间int findTargetSumWays(vectorint nums, int target) {int sum0,nnums.size();for(const int x:nums) sumx;if (abs(target) sum) return 0; // 此时没有方案if ((sum target) % 2 1) return 0; // 此时没有方案int addTarget (sum target) / 2;vectorintf(addTarget1,0);f[0]1;for(int i0;in;i) {for(int caddTarget;cnums[i];c--) {f[c]f[c] f[c-nums[i]];}}return f[addTarget];}
};// 也可以写成这样
for(const int x:nums) {for(int caddTarget;cx;c--) {f[c]f[c] f[c-x];}
}
