leetcode刷题笔记: 1785 minimum-elements-to-add-to-form-a-given-sum

2022-12-16 12:31 作者:StepfenShawn 0人读过 | 我要投稿

好久没写博客了，今天就写篇博客记录一下leetcode上的每日一题吧! 这其实是一道数学题(贪心算法严格上是运筹学的内容，也可以说是数学吧), 我会带大家从 0 开始证明贪心算法的性质。

题目地址:

https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum/

minimum-elements-to-add-to-form-a-given-sum

You are given an integer array nums and two integers limit and goal. The array nums has an interesting property that abs(nums[i]) <= limit.

Return the minimum number of elements you need to add to make the sum of the array equal to goal. The array must maintain its property that abs(nums[i]) <= limit.

Note that abs(x) equals x if x >= 0, and -x otherwise.

Example 1:

Input: nums = [1,-1,1], limit = 3, goal = -4

Output: 2

Explanation: You can add -2 and -3, then the sum of the array will be 1 - 1 + 1 - 2 - 3 = -4.

Example 2:

Input: nums = [1,-10,9,1], limit = 100, goal = 0

Output: 1

题目大意是给你一个数组 nums 和两个变量 limit, goal, 其中 nums 里面的每一个值 $x$ 都要满足其绝对值 $%7Cx%7C%20%3C%3D$ limit, 要求的是向里面添加最少多少个元素使得和等于 goal。(注意添加的元素也要满足nums的性质)。

证明该问题的贪心性质

题目要求我们添加的元素尽可能少，首先我们先考虑动态规划是否能解决这个问题，首先我们把问题化为最小规模(这是动规和贪心最重要的思想), 也就是考虑我们只需添加一个元素时, 假设这个元素为 $m$ , 那么 $m$ 必定属于 $%5B1%2C%20limit%5D$ , 注意这里 $m$ 不能为 0，因为将 0 添加进去对答案并没有贡献, 并且还违背了添加的次数尽可能少的原则。

我们确定了子问题中添加进去的 $m$ 的范围后, 我们还需要证明这个问题的最优子结构(无论是动态规划还是贪心问题都需要这一步，否则无法使用这两种算法)。

假设我们得到了一组要添加的元素的解 $(m1%2C%20m2%2C%20m3%2C...)$ 并且这组解是最优解, 如果我们找到了另外一组解 $(m1'%2C%20m2'%2C%20m3'%2C%20...)$ 比 $(m1%2C%20m2%2C%20m3%2C...)$ 更优(在题目里面指的是长度最短), 那么与假设 $(m1%2C%20m2%2C%20m3%2C...)$ 是最优解矛盾了。所以我们通过反证法证明了该问题具有最优子结构。

证明了最优子结构，我们观察子问题的关系可知当我们每次选择添加的元素 $m$ 等于 limit 时得到的一定是最优解(这可以用反证法证明), 为什么呢，我们可以从直观上理解，假如我选择了一个值为 $limit$ 的元素添加到了nums中, 如果此时数组的和 $sum'$ 大于 $sum$ , 那么我们也一定能添加一个比limit小的元素，如果 $sum'$ <= $sum$ 了 , 那么这样的选择会保证整个过程的次数是最少的，然而贪心算法的思想就是每次都做出最优的选择, 那么我们就可以使用贪心算法了：