मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जहां प्रत्येक मान एक कार्य को पूरा करने में लगने वाली समय इकाई निर्धारित करता है। हम किसी भी गैर-लगातार कार्यों को छोड़ सकते हैं, हमें सभी कार्यों को पूरा करने में लगने वाला न्यूनतम समय ढूंढना है।
उदाहरण के लिए, यदि इनपुट nums = [11, 6, 8, 16] है, तो आउटपुट 14 होगा, क्योंकि हम पहले और अंतिम कार्यों को छोड़ सकते हैं।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- n := nums का आकार
- table := एक n x 2 मैट्रिक्स बनाएं और इसे 0 से भरें
- table[0, 0] := 0
- table[0, 1] := nums[0]
- i को 1 से n - 1 तक के लिए, करें
- table[i, 0] := table[i - 1, 1]
- table[i, 1] = (table[i - 1, 0] और table[i - 1][1] में से न्यूनतम) + nums[i]
- table पंक्ति [n - 1] का न्यूनतम लौटाएं
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
उदाहरण
class Solution:
def solve(self, nums):
n = len(nums)
table = [[0] * 2 for _ in range(n)]
table[0][0] = 0
table[0][1] = nums[0]
for i in range(1, n):
table[i][0] = table[i - 1][1]
table[i][1] = min(table[i - 1][0], table[i - 1][1]) + nums[i]
return min(table[n - 1])
ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))
इनपुट
[11, 6, 8, 16]
आउटपुट
14