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

╰半橙微兮° 2024-02-05 17:47 52阅读 0赞

## 494. 目标和 ##

[494. 目标和][494.]

### 题目描述： ###

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

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

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

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

![19c4ce41eae049f5b812348221c6c198.png][]

### 解题思路： ###

算法思路：

本题可以直接⽤「暴搜」的⽅法解决。但是稍微⽤数学知识分析⼀下，就能转化成我们常⻅的「背

包模型」的问题。

设我们最终选取的结果中，前⾯加 + 号的数字之和为  a  ，前⾯加 - 号的数字之和为  b  ，整个数组

的总和为  sum  ，于是我们有：

▪  a + b = sum

▪  a - b = target

上⾯两个式⼦消去  b  之后，可以得到  a = (sum + target) / 2

也就是说，我们仅需在  nums  数组中选择⼀些数，将它们凑成和为  (sum + target) / 2  即

可。

问题就变成了  416. 分割等和⼦集  这道题。

我们可以⽤相同的分析模式，来处理这道题。

1.  状态表⽰：

dp\[i\]\[j\]  表⽰：在前  i  个数中选，总和正好等于  j  ，⼀共有多少种选法。

2.  状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不

选择」最后⼀个元素两种策略：

i.  不选  nums\[i\]  ：那么我们凑成总和  j  的总⽅案，就要看在前  i - 1  个元素中选，凑

成总和为  j  的⽅案数。根据状态表⽰，此时  dp\[i\]\[j\] = dp\[i - 1\]\[j\]  ；

ii.  选择  nums\[i\]  ：这种情况下是有前提条件的，此时的  nums\[i\]  应该是⼩于等于  j  。

因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们能够凑成总和为

j  的⽅案数，就要看在前  i - 1  个元素中选，能否凑成总和为  j - nums\[i\]  。根据

状态表⽰，此时  dp\[i\]\[j\] = dp\[i - 1\]\[j - nums\[i\]\]

综上所述，两种情况如果存在的话，应该要累加在⼀起。因此，状态转移⽅程为：

dp\[i\]\[j\] = dp\[i - 1\]\[j\]

if(nums\[i - 1\] <= j) dp\[i\]\[j\] = dp\[i\]\[j\] += dp\[i - 1\]\[j - nums\[i

\- 1\]\]

3.  初始化：

由于需要⽤到「上⼀⾏」的数据，因此我们可以先把第⼀⾏初始化。

第⼀⾏表⽰不选择任何元素，要凑成⽬标和  j  。只有当⽬标和为  0  的时候才能做到，因此第⼀

⾏仅需初始化第⼀个元素  dp\[0\]\[0\] = 1

4.  填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5.  返回值：

根据「状态表⽰」，返回  dp\[n\]\[aim\]  的值。

其中  n  表⽰数组的⼤⼩，  aim  表⽰要凑的⽬标和。

6.  空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。

对于 01背包类型的，我们的优化策略是：

i.  删掉第⼀维；

ii.  修改第⼆层循环的遍历顺序即可。

### 解题代码： ###

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][1049. _ II]

### 题目描述： ###

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

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

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

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

### 解题思路： ###

算法思路：

先将问题「转化」成我们熟悉的题型。

▪  任意两块⽯头在⼀起粉碎，重量相同的部分会被丢掉，重量有差异的部分会被留下来。那就

相当于在原始的数据的前⾯，加上「加号」或者「减号」，是最终的结果最⼩即可。也就是

说把原始的⽯头分成两部分，两部分的和越接近越好。

▪  ⼜因为当所有元素的和固定时，分成的两部分越接近数组「总和的⼀半」，两者的差越⼩。

因此问题就变成了：在数组中选择⼀些数，让这些数的和尽量接近  sum / 2  ，如果把数看成物

品，每个数的值看成体积和价值，问题就变成了「01 背包问题」。

1.  状态表⽰：

dp\[i\]\[j\]  表⽰在前  i  个元素中选择，总和不超过 j，此时所有元素的「最⼤和」。

2.  状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，分情况讨论：

i.  不选  stones\[i\]  ：那么我们是否能够凑成总和为  j  ，就要看在前  i - 1  个元素中

选，能否凑成总和为  j  。根据状态表⽰，此时  dp\[i\]\[j\] = dp\[i - 1\]\[j\]  ；

ii.  选择  stones\[i\]  ：这种情况下是有前提条件的，此时的  stones\[i\]  应该是⼩于等于

j  。因为如果这个元素都⽐要凑成的总和⼤，选择它就没有意义呀。那么我们是否能够凑

成总和为  j  ，就要看在前  i - 1  个元素中选，能否凑成总和为  j - stones\[i\]  。根

据状态表⽰，此时  dp\[i\]\[j\] = dp\[i - 1\]\[j - stones\[i\]\] + stones\[i\]  。

综上所述，我们要的是最⼤价值。因此，状态转移⽅程为：

dp\[i\]\[j\] = dp\[i - 1\]\[j\]

if(j >= stones\[i\]) dp\[i\]\[j\] = dp\[i\]\[j\] + dp\[i - 1\]\[j - stones\[i\]\]

\+ stones\[i\]  。

3.  初始化：

由于需要⽤到上⼀⾏的数据，因此我们可以先把第⼀⾏初始化。

第⼀⾏表⽰「没有⽯⼦」。因此想凑成⽬标和  j  ，最⼤和都是  0  。

4.  填表顺序：

根据「状态转移⽅程」，我们需要「从上往下」填写每⼀⾏，每⼀⾏的顺序是「⽆所谓的」。

5.  返回值：

a.  根据「状态表⽰」，先找到最接近  sum / 2  的最⼤和  dp\[n\]\[sum / 2\]  ；

b.  因为我们要的是两堆⽯⼦的差，因此返回  sum - 2 \* dp\[n\]\[sum / 2\]  。

6.  空间优化：

所有的背包问题，都可以进⾏「空间」上的优化。

对于 01背包类型的，我们的优化策略是：

i.  删掉第⼀维；

ii.  修改第⼆层循环的「遍历顺序」即可。

### 解题代码： ###

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];
     }
    };

[494.]: https://leetcode.cn/problems/target-sum/
[19c4ce41eae049f5b812348221c6c198.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/491fba62d9134cb580d43074cd882cda.png
[1049. _ II]: https://leetcode.cn/problems/last-stone-weight-ii/