Combination Sum
Տրված
N թիվը և թույլատրելի դրական թվերից կազմված զանգված։ Ձեզ խնդրում են հաշվել, թե քանի տարբեր եղանակով է կարելի գրել N-ը որպես այդ թվերի գումար։Օրինակ, եթե թույլատրելի թվերը
[1, 2, 3]-ն են, իսկ N-ը 4 է, ապա այդ թվերը գումարելով 4-ը կարելի է ստանալ 7 տարբեր եղանակով.4 ստանալու 7 տարբերակները 1, 2, 3 թվերի միջոցով
- 1 + 1 + 1 + 1
- 1 + 1 + 2
- 1 + 2 + 1
- 2 + 1 + 1
- 1 + 3
- 3 + 1
- 2 + 2
Սա Դինամիկ Ծրագրավորուման դասական խնդիր է, որը կարելի է լուծել
d[sum] վիճակ պահելով, որը ներկայացնում է, թե քանի եղանակով կարող ենք հասնել sum-ին օգտագործելով թույլատրելի թվերը.N = ...
nums = [...]
d = [0] * (N + 1) # d[i] = բոլոր հնարավոր կոմբինացիաները, որոնք գումարելով ստանում ենք i
d[0] = 1 # Գոյություն ունի 0 ստանալու 1 տարբերակ - ոչ մի թիվ չօգտագործելը
for i in range(1, N + 1): # Փորձում ենք հերթականությամբ ստանալ բոլոր գումարները 1...N
for num in nums: # Փորձում ենք num-ի օգնությամբ ստանալ d[i]
if i - num >= 0: # Եթե հնարավոր է i ստանալ num-ի միջոցով
d[i] += d[i - num]
print(d[N])Այսպիսով, մեր
d[i] վիճակը ցույց է տալիս, թե քանի եղանակով կարող ենք ստանալ i թիվը թույլատրելի թվերի (nums-ի) միջոցով։ Սկզբում բոլոր դիրքերի վիճակը 0 է, բացի d[0]-ից, որն ստանում է 1 արժեքը, քանի որ 0 ստանալու մեկ տարբերակ կա – ոչ մի թիվ չօգտագործել։ Մնացած թվերի համար ստուգում ենք բոլոր հնարավոր տարբերակները, թե ինչպես կարող ենք ստանալ այդ թվերը՝ օգտագործելով nums-ի անդամները։Օրինակ, եթե մենք կարող ենք 11 (
d[11]) ստանալ 5 տարբեր ձևով, և գիտենք, որ 8 (d[8]) ստացվել էր 3 տարբեր ձևով, ապա, եթե 3-ն առկա է nums-ում, 11-ը կարելի է ստանալ արդեն հայտնի բոլոր 5 ձևերով, ինչպես նաև 3 նոր ձևով, որոնք ներառում են 8-ի ստացման տարբերակները:Եկեք տեսնենք թե ինչպես ալգորիթմը կաշխատի մեր օրինակի վրա.
nums = [1, 2, 3] և N = 4
d = [1, 0, 0, 0, 0]→ 1 եղանակ 0 ստանալու (ոչինչ չվերցնել), իսկ մնացածը 0
i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0
i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0
i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]
i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]
print(d[4])→ տպում է 7
Առաջադրանք - Զառի Կոմբինացիաները
Զառը ցույց է տալիս 1-ից 6 ցանկացած թիվ։ Ձեզ խնդրում են հաշվել, թե քանի տարբեր եղանակով կարելի է ստանալ
n-ը, եթե կրկնվող զառի նետումները գումարվում են իրար։
Մուտք
Մուտքը պարունակում է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ):Ելք
Ծրագիրը պետք է տպի, թե քանի եղանակով կարելի է զառի նետումները գումարելով ստանալ
n թիվը։ Քանի որ պատասխանը կարող է լինել շատ մեծ, անհրաժեշտ է տպել պատասխանը -ի վրա բաժանելիս ստացվող մնացորդը։Օրինակներ
Մուտք | Ելք |
2 | 2 |
3 | 4 |
Բացատրություն
- 2 → 1 + 1, 2
- 3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB