मान लीजिए हमारे पास एक संख्या n है, हमें (3 x n) ब्लॉक को 1 x 2 डोमिनोज से भरने के तरीकों की संख्या ढूंढनी है। हम आवश्यकता पड़ने पर डोमिनोज को घुमा सकते हैं। यदि उत्तर बहुत बड़ा है तो इसे 10^9 + 7 से मॉड करें।
उदाहरण के लिए, यदि इनपुट n = 4 है, तो आउटपुट 11 होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम डायनामिक प्रोग्रामिंग और रिकरेंस रिलेशन का उपयोग करेंगे:
- m = 10^9 + 7
- यदि n विषम है, तो 0 लौटाएं
- cs := 1, os := 0
- i को 2 से n तक, 2 से बढ़ाते हुए लूप चलाएं:
- cs := 3 * cs + os
- os := 2 * cs + os
- cs mod m लौटाएं
पायथन कार्यान्वयन
class Solution:
def solve(self, n):
m = (10 ** 9 + 7)
if n % 2 == 1:
return 0
cs = 1
os = 0
for i in range(2, n + 1, 2):
cs, os = (3 * cs + os, 2 * cs + os)
return cs % m
ob = Solution()
n = 4
print(ob.solve(n))इनपुट
4
आउटपुट
11