LeetCode解題筆記-6 Combination Sum IV

LeetCode中的Combination Sum IV 這題我最後沒有解出來,之前在刷LeetCode的題目時,還是會常常想要依靠自己的腦袋去解題,所以會用很直觀的方式去思考,但隨著接觸到的題目越來越難,有些思路真的是會需要先參考他人的答案才有可能去做解答,對於第一個想出來的人真的很佩服,廢話不多說,來看題目吧!

LeetCode Combination Sum IV 題目詳解

老樣子,中文翻譯為給定一個陣列和一個目標數字,找出陣列內的元素加總等於目標數字的方法總共有幾個,並且不同位置的組合也要算進去,也就是[1,3]和[3,1]是不一樣的。

首先這題的困難點在於,直觀想法是很難去轉換成程式的,也就是你在現實中給你紙和筆你怎麼解答這題,你其實是沒有規律的一直湊數字,很難有一個統整的想法出來,所以我最後也是卡在這裡就敗倒了,接下來我就來把我理解過後他人的解題方法思路來做詳解,這邊放上思路的出處

https://blog.csdn.net/fuxuemingzhu/article/details/79343825

首先我們必須要先從一個點去思考,

假設我們能夠知道這個陣列中組合成1,2,3的可能性有多少個,我們便可以去繼續4(target)的組合有多少個

什麼意思呢? 4有以下幾個組合 0+4 / 1+3 / 2+2 / 3+1 / 4+0 而首先我們先不考慮前後兩者,因為4並不存在於陣列內,則我們思考一下 以1+3來說,3的組合我們發現有4個所以 1*4 = 4 ,而2+2的組合我們發現2的組合有2個,1*2乙次類推最後就會得到4的組和有7個也就是正確答案,可能會有同學問說

1+3不應該是 1的組合+3的組合嗎?

這邊我們要思考的是,如果前面那個數字也放進去做組合的話,則答案就會重複譬如 2+2拆成 1+1+1+1 =而 1+3也同樣拆成1+1+1+1則這樣就沒有意義了,反而如果前面的數字不能懂的話,則從順序上是得不到重複的答案的,

那我們要怎麼去算組合呢?這邊我們就可以來看程式碼

dp = [0] * (target + 1)
dp[0] = 1

首先我們先宣告一個數組dp,其意義為dp[i]就是代表i有多少種陣列組合

for i in range(1, target + 1):
    for num in nums:
        if i >= num:
            #dp[1] = dp[0] 
            #dp[2] = dp[2]+dp[2-1]
            #dp[2] = dp[2]+dp[2-2]
            #dp[3] = dp[3]+dp[3-1]
            #dp[3] = dp[3]+dp[3-2]
            #dp[3] = dp[3]+dp[3-3]
            dp[i] += dp[i - num]
return dp.pop()

此處我們可以來觀察一下他是如何計算的,首先i的range代表去遍歷1~target,再來num則是陣列內的元素,而每當i>=num,也就是說num有可能組合成i的時候,這邊讓dp[i] = dp[i] + dp[i-num],是什麼意思呢?我們思考剛剛說的,以dp[3]為例子,當遇到num = 1時,我們可以將組合想像成 1+2,所以只要將dp[3-1]=2的組合可能數目就會是dp[3]的可能數目,而再來當num=2時,組合就會變成2+1,所以只要加入dp[3-2] =1的組合可能數目,也會是dp[3]的可能數目,到最後則是num =3 時,加入dp[0]的可能數目,這三者加總就會是dp[3]的全部可能數目,最後類推到dp[4]就會得到答案了。

這題在思考上真的很難單純用直觀方法想出來,我覺得屬於你必須要持續刷LeetCode有一定的解題經驗才能想出來的題目,那今天的講解就到這裡!

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。