পাইথনে দুটি লিস্ট থেকে ফাইনাল ইন্ডেক্সে পৌঁছানোর ন্যূনতম খরচ বের করার প্রোগ্রাম

দুটি সমান দৈর্ঘ্যের লিস্ট nums0, nums1 এবং দুটি মান d (ডিস্ট্যান্স), c (সুইচিং খরচ) দেওয়া আছে। ইন্ডেক্স ০ থেকে যেকোনো একটি লিস্টে শুরু করে যেকোনো একটি লিস্টের শেষ ইন্ডেক্সে পৌঁছাতে হবে। প্রতিটি রাউন্ডে:

একই লিস্টে থাকলে d দূরত্ব পর্যন্ত ফরোয়ার্ড যেতে পারেন।
লিস্ট সুইচ করতে c খরচ।
ল্যান্ড করার খরচ = সেই সেলের ভ্যালু।

ন্যূনতম মোট খরচ বের করতে হবে।

উদাহরণস্বরূপ, nums0=[2,3,10,10,6], nums1=[10,10,4,5,100], d=2, c=3 হলে আউটপুট ১৮। পথ: ২ (nums0) → সুইচ → ৪ (nums1) → সুইচ → ৬ (nums0) = ১২ + ২×৩ = ১৮।

সমাধানের পদ্ধতি (রিকার্সিভ DFS + মেমোরাইজেশন)

switch = {0: nums0, 1: nums1}।
search(idx, nums) ফাংশন:
- বেস: idx >= len → inf; idx == last → ভ্যালু।
- c = inf।
- i = 1..d লুপ: c = min(c, switch[nums][idx] + search(idx+i, nums)) এবং c = min(c, switch[nums][idx] + cost + search(idx+i, 1-nums))।
- c রিটার্ন।
min(search(0,0), search(0,1)) রিটার্ন করুন।

নোট: এই রিকার্সিভ সমাধান এক্সপোনেনশিয়াল। DP/মেমোরাইজেশন দিয়ে অপ্টিমাইজ করা উচিত।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, nums0, nums1, dist, cost):
        switch = {0: nums0, 1: nums1}
        def search(idx, nums):
            if idx >= len(switch[nums]):
                return float("inf")
            if idx == len(switch[nums]) - 1:
                return switch[nums][-1]
            c = float("inf")
            for i in range(1, dist + 1):
                c = min(c, switch[nums][idx] + search(idx + i, nums))
                c = min(c, switch[nums][idx] + cost + search(idx + i, int(not nums)))
            return c
        return min(search(0, 0), search(0, 1))

ob = Solution()
nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3
print(ob.solve(nums0, nums1, d, c))

ইনপুট

[2,3,10,10,6], [10,10,4,5,100], 2, 3