leetCode 494. 目标和 + 动态规划 + 记忆化搜索 + 递推 + 空间优化

记忆化搜索 + 递推 + 空间优化"/>

leetCode 494. 目标和 + 动态规划 + 记忆化搜索 + 递推 + 空间优化

关于本题我的往期文章：

LeetCode 494.目标和 （动态规划 + 性能优化）二维数组 压缩成 一维数组_呵呵哒(￣▽￣)"的博客-CSDN博客

给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

（1）递归 

class Solution {
public:// 递归int findTargetSumWays(vector<int>& nums, int target) {int sum=0,n=nums.size();for(const int & x:nums) sum+=x;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;function<int(int,int)> dfs = [&](int i,int c) -> int {if(i<0) return c==0 ? 1 : 0;// 边界条件：由于要求是恰好组成。恰好情况：当c=0的时候，才能返回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(vector<int>& nums, int target) {int sum=0,n=nums.size();for(const int & x:nums) sum+=x;if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案int addTarget = (sum + target) / 2;vector<vector<int>> memo(n+1,vector<int>(addTarget+1,-1));function<int(int,int)> dfs = [&](int i,int c) -> int {if(i<0) return c==0 ? 1 : 0;int &res = memo[i][c];if(res != -1) return res;if(c-nums[i]<0) return res=dfs(i-1,c);return res=dfs(i-1,c) + dfs(i-1,c-nums[i]);};return dfs(n-1,addTarget);}
};

（3）1: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[i+1][c] = f[i][c] + f[i][c-w[i]]

初始化：根据 if(i<0) return c==0 ? 1 : 0; 

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

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

class Solution {
public:// 递推式int findTargetSumWays(vector<int>& nums, int target) {int sum=0,n=nums.size();for(const int & x:nums) sum+=x;if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案int addTarget = (sum + target) / 2;vector<vector<int>> f(n+1,vector<int>(addTarget+1,0));f[0][0]=1;for(int i=0;i<n;i++) {for(int c=0;c<=addTarget;c++) {if(c-nums[i]<0) f[i+1][c]=f[i][c];else f[i+1][c]=f[i][c] + f[i][c-nums[i]];}}return f[n][addTarget];}
};

• 优化空间

方式一：二维数组优化

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

class Solution {
public:// 递推式 + 优化空间int findTargetSumWays(vector<int>& nums, int target) {int sum=0,n=nums.size();for(const int & x:nums) sum+=x;if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案int addTarget = (sum + target) / 2;vector<vector<int>> f(2,vector<int>(addTarget+1,0));f[0][0]=1;for(int i=0;i<n;i++) {for(int c=0;c<=addTarget;c++) {if(c-nums[i]<0) f[(i+1)%2][c]=f[i%2][c];else f[(i+1)%2][c]=f[i%2][c] + f[i%2][c-nums[i]];}}return f[n%2][addTarget];}
};

方式二：一维数组优化

• f[i+1][c]=f[i][c] + f[i][c-nums[i]];
• f[c]=f[c] + f[c-nums[i]];

class Solution {
public:// 递推式 + 优化空间int findTargetSumWays(vector<int>& nums, int target) {int sum=0,n=nums.size();for(const int & x:nums) sum+=x;if (abs(target) > sum) return 0; // 此时没有方案if ((sum + target) % 2 == 1) return 0; // 此时没有方案int addTarget = (sum + target) / 2;vector<int>f(addTarget+1,0);f[0]=1;for(int i=0;i<n;i++) {for(int c=addTarget;c>=nums[i];c--) {f[c]=f[c] + f[c-nums[i]];}}return f[addTarget];}
};// 也可以写成这样
for(const int& x:nums) {for(int c=addTarget;c>=x;c--) {f[c]=f[c] + f[c-x];}
}