494. 目标和
思路
首先,将这道题想成 0-1背包问题,我们最终要输出的结果是最多的方法数,因此 dp 数组需要记录具体的方法数。
状态定义
按照 0-1 背包问题的套路,我们将状态定义为 :dp[i][j]
,表示「前 i 个数字,和等于 j 的情况下,能够达到的不同表达式的最大数目」。
状态转移方程
我们以 nums = [1, 1, 1]
为例,很容易可以发现: dp[i][j] 取决于「前 i-1 个元素的和」与「当前元素的值」的关系 ,我们要从某个值得到 j,j 可以由该值加上 nums[i]得到,也可以由该值减去 nums[i]得到 。即 dp[i][j] = dp[i-1][j-nums[i-1]] + dp[i-1][j+nums[i-1]];
进一步思考:下标转换
但是从上面的例子可以看出,和可能为负数 ,而下标不可能小于 0,那么我们如何防止下标越界呢?
我们不妨改变下标的取值范围,对于 nums = [1, 1, 1]
来说,我们先计算它的最大和:3(1+1+1)
,记为 sum
,运算结果的取值范围是:[-3,3],我们可以对这个范围的数都加上 sum ,变成 [0, 6],这样就解决了下标越界的问题。
所以最终的状态转移方程为:dp[i][j+sum] += dp[i-1][j-nums[i-1]+sum];
,dp[i][j+sum] += dp[i-1][j+nums[i-1]+sum];
,凡是 j 值我都加上了 sum。
初始化
我们需要初始化 nums[0] 可以构造出的运算结果,即 dp[1][nums[0]+sum] += 1, dp[1][-nums[0]+sum] += 1;
。
这里需要考虑 +nums[0]
和 -nums[0]
两种情况,我没有直接置为 1 ,是因为考虑到 nums[0] = 0
的情况,+0 和 -0 分别代表运算结果为 0 的两种表达式,这种代码书写方式更为通用。
此外,为了防止下标越界,我将 j 值加上了 sum。文章来源:https://www.toymoban.com/news/detail-435419.html
最终的返回结果
最终返回 n 个数字,和等于 target 的情况下能达到的不同表达式的最大数目,同样地,target 也需要加上 sum ,即dp[n][target+sum];
。文章来源地址https://www.toymoban.com/news/detail-435419.html
注意点
- 为了方便计算,我们在开头进行特殊判断,如果 sum 小于 target 的绝对值,说明无法构造出表达式,直接返回 0;
- 需要判断 j 的边界,不然很容易出现下标越界的问题。
代码
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
// 特判:不可能构造出表达式
if(sum < abs(target)) return 0;
int n = nums.size();
vector<vector<int>> dp(n+1, vector<int>(sum*2+1, 0));
// 初始化
// 通过nums[0]能够构造出一种等于target的表达式 +1
dp[1][nums[0]+sum] += 1, dp[1][-nums[0]+sum] += 1;
for(int i=2; i<=n; ++i){
for(int j=-sum; j<=sum; ++j){
if(j-nums[i-1]+sum>=0 && j-nums[i-1]+sum<=sum*2 && dp[i-1][j-nums[i-1]+sum] > 0){
dp[i][j+sum] += dp[i-1][j-nums[i-1]+sum];
}
if(j+nums[i-1]+sum>=0 && j+nums[i-1]+sum<=sum*2 && dp[i-1][j+nums[i-1]+sum] > 0){
dp[i][j+sum] += dp[i-1][j+nums[i-1]+sum];
}
}
}
return dp[n][target+sum];
}
};
到了这里,关于【LeetCode】494. 目标和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!