পাইথনে মিন কস্ট ক্লাইমবিং স্টেয়ার্স (Min Cost Climbing Stairs)

সমস্যা বিবরণ

একটি সিঁড়ির প্রতিটি ধাপের একটি কস্টあり। আপনি ০ বা ১ নম্বর ধাপ থেকে শুরু করতে পারেন। প্রতিবার ১ বা ২ ধাপ উঠতে পারেন। শীর্ষে পৌঁছানোর ন্যূনতম কস্ট বের করুন।

উদাহরণ

cost = [12,17,20] → আউটপুট: 17

ধাপ ১ (কস্ট ১৭) থেকে শুরু করে সরাসরি শীর্ষে যাওয়া সেরা।

এলগরিদম (Dynamic Programming)

1. dp[i] = i-নম্বর ধাপে পৌঁছার ন্যূনতম কস্ট।
2. dp[0] = cost[0], dp[1] = cost[1]।
3. i = 2 থেকে n-1 পর্যন্ত: dp[i] = cost[i] + min(dp[i-1], dp[i-2])।
4. উত্তর = min(dp[n-1], dp[n-2]) (শেষ বা শেষ থেকে দ্বিতীয় ধাপ থেকে শীর্ষে যেতে পারে)।

পাইথন বাস্তবায়ন

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        if n <= 2:
            return min(cost)
        dp = [0] * n
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
        return min(dp[-1], dp[-2])

ob = Solution()
print(ob.minCostClimbingStairs([12, 17, 20]))  # 17

ইনপুট / আউটপুট

ইনপুট: [12, 17, 20]
আউটপুট: 17