【算法挨揍日记】day42——494. 目标和、1049. 最后一块石头的重量 II

494. 目标和

494.?目标和

题目描述：

给你一个非负整数数组?nums?和一个整数?target?。

向数组中的每个整数前添加?'+'?或?'-'?，然后串联起所有整数，可以构造一个?表达式?：

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

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

解题思路：

解题代码：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(auto x : nums) sum += x;
        int a=(sum+target)/2;
        int n=nums.size();
        if(a<0||(sum+target)%2) return 0;
        vector<int>dp(a+1);
        dp[0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=a;j>=nums[i-1];j--)
                    dp[j]+=dp[j-nums[i-1]];
        }
        return dp[a];
    }
};

1049. 最后一块石头的重量 II

1049.?最后一块石头的重量 II

题目描述：

有一堆石头，用整数数组?stones?表示。其中?stones[i]?表示第?i?块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为?x?和?y，且?x <= y。那么粉碎的可能结果如下：

• 如果?x == y，那么两块石头都会被完全粉碎；
• 如果?x != y，那么重量为?x?的石头将会完全粉碎，而重量为?y?的石头新重量为?y-x。

最后，最多只会剩下一块?石头。返回此石头?最小的可能重量?。如果没有石头剩下，就返回?0。

解题思路：

解题代码：

class Solution
{
public:
 int lastStoneWeightII(vector<int>& stones) 
 {
 // 1. 准备?作
 int sum = 0;
 for(auto x : stones) sum += x;
 int n = stones.size(), m = sum / 2;
 // 2. dp
 vector<int> dp(m + 1);
 for(int i = 1; i <= n; i++)
 for(int j = m; j >= stones[i - 1]; j--)
 dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
 // 3. 返回结果
 return sum - 2 * dp[m];
 }
};