मान लीजिए हमारे पास bricks नामक संख्याओं की एक सूची है और दो अन्य मान width और height हैं। bricks[i] में प्रत्येक तत्व एक ईंट का प्रतिनिधित्व करता है जिसकी लंबाई bricks[i] इकाई है और चौड़ाई 1 इकाई है। हमें ईंटों को बिछाने के तरीकों की संख्या ढूंढनी है ताकि हमें दी गई चौड़ाई और ऊंचाई के साथ ईंटों का पूरा लेआउट मिले। हम ईंटों का पुन: उपयोग कर सकते हैं लेकिन उन्हें केवल क्षैतिज रूप से बिछाया जा सकता है।
इसलिए, यदि इनपुट है bricks = [2, 1], width = 3, height = 2, तो आउटपुट होगा 9 क्योंकि:
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
w :=आकारwidthके समान एक सूची और पहली स्थिति में 1 डालें, बाकी 0iके लिए 0 सेwidthतक की रेंज में, करें:- यदि
w[i]शून्येतर है, तो:bricksमें प्रत्येकxके लिए, करें:- यदि
i + x <= width, तो:w[i + x] := w[i + x] + w[i]
- यदि
- यदि
w[width]^heightलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def solve(bricks, width, height):
w = [1] + [0] * width
for i in range(width):
if w[i]:
for x in bricks:
if i + x <= width:
w[i + x] += w[i]
return w[width] ** height
bricks = [2, 1]
width = 3
height = 2
print(solve(bricks, width, height))
इनपुट
[2, 1], 3, 2
आउटपुट
9