好久沒寫博客了，今天就寫篇博客記錄一下leetcode上的每日一題吧! 這其實(shí)是一道數(shù)學(xué)題(貪心算法嚴(yán)格上是運(yùn)籌學(xué)的內(nèi)容，也可以說是數(shù)學(xué)吧), 我會帶大家從 0 開始證明貪心算法的性質(zhì)。

題目地址:

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

題目大意是給你一個(gè)數(shù)組 nums 和兩個(gè)變量 limit, goal, 其中 nums 里面的每一個(gè)值 都要滿足?其絕對值 limit, 要求的是向里面添加最少多少個(gè)元素使得和等于 goal。(注意添加的元素也要滿足nums的性質(zhì))。

證明該問題的貪心性質(zhì)

題目要求我們添加的元素盡可能少，首先我們先考慮動態(tài)規(guī)劃是否能解決這個(gè)問題，首先我們把問題化為最小規(guī)模(這是動規(guī)和貪心最重要的思想),?也就是考慮我們只需添加一個(gè)元素時(shí), 假設(shè)這個(gè)元素為?, 那么? 必定屬于, 注意這里?不能為 0， 因?yàn)閷?0 添加進(jìn)去對答案并沒有貢獻(xiàn), 并且還違背了添加的次數(shù)盡可能少的原則。

我們確定了子問題中添加進(jìn)去的??的范圍后, 我們還需要證明這個(gè)問題的最優(yōu)子結(jié)構(gòu)(無論是動態(tài)規(guī)劃還是貪心問題都需要這一步，否則無法使用這兩種算法)。

假設(shè)我們得到了一組要添加的元素的解 并且這組解是最優(yōu)解, 如果我們找到了另外一組解 ??比??更優(yōu)(在題目里面指的是長度最短), 那么與假設(shè)?是最優(yōu)解矛盾了。所以我們通過反證法證明了該問題具有最優(yōu)子結(jié)構(gòu)。?

證明了最優(yōu)子結(jié)構(gòu)，我們觀察子問題的關(guān)系可知當(dāng)我們每次選擇添加的元素? 等于 limit 時(shí)得到的一定是最優(yōu)解(這可以用反證法證明), 為什么呢，我們可以從直觀上理解，假如我選擇了一個(gè)值為 的元素添加到了nums中, 如果此時(shí)數(shù)組的和大于, 那么我們也一定能添加一個(gè)比limit小的元素，如果 ?<=?了?,?那么這樣的選擇會保證整個(gè)過程的次數(shù)是最少的，然而貪心算法的思想就是每次都做出最優(yōu)的選擇, 那么我們就可以使用貪心算法了：

上面的代碼時(shí)間復(fù)雜度有點(diǎn)高， 我們發(fā)現(xiàn) while 循環(huán)有點(diǎn)像在做除法， 其實(shí)我們得答案為

?

由于 c++ 里面 int 相除是向下取整, 那么我們可以把這個(gè)式子化簡成 向下取整：

,?