পাইথনে সিঁড়ি ওঠার ন্যূনতম খরচ

ধরুন একটি সিঁড়ি আছে, এখানে i-th ধাপে কিছু নন-নেতিবাচক খরচ মান খরচ [i] নির্ধারিত হবে। যখন আমরা খরচ পরিশোধ করি, আমরা হয় এক বা দুই ধাপে উঠতে পারি। ফ্লোরের শীর্ষে পৌঁছানোর জন্য আমাদের ন্যূনতম খরচ খুঁজে বের করতে হবে, এবং আমরা হয় সূচক 0 দিয়ে ধাপ থেকে শুরু করতে পারি, অথবা সূচক 1 দিয়ে ধাপ থেকে শুরু করতে পারি।

সুতরাং, যদি ইনপুটটি খরচের মত হয় =[12,17,20], তাহলে আউটপুট হবে 17, ধাপ 1 থেকে শুরু করার জন্য সবচেয়ে সস্তা অবস্থান কারণ আমাদের সেই খরচ দিতে হবে এবং শীর্ষে যেতে হবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

dp :=খরচের সমান আকারের একটি অ্যারে, এবং 0 দিয়ে পূরণ করুন
dp[0] :=খরচ[0]
যদি খরচের আকার>=2, তাহলে
- dp[1] :=খরচ[1]
আমার জন্য রেঞ্জ 2 থেকে খরচের আকার - 1, করুন
- dp[i] :=খরচ[i] + ন্যূনতম dp[i-1], dp[i-2]
সর্বনিম্ন dp[-1], dp[-2] ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def minCostClimbingStairs(self, cost):
      dp = [0] * len(cost)
      dp[0] = cost[0]
      if len(cost) >= 2:
         dp[1] = cost[1]
      for i in range(2, len(cost)):
         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]))

ইনপুট

[12,17,20]