সমস্যা বিবরণ
stairs লিস্টে প্রতিটি ইনডেক্সের খরচ দেওয়া আছে। ইনডেক্স ০ থেকে শুরু করে শেষ ইনডেক্সে যেতে হবে। প্রতিটি ধাপে ১ থেকে k ধাপ কूदতে পারেন। ন্যূনতম মোট খরচ বের করতে হবে।
উদাহরণ
stairs = [4, 11, 11, 3, 2], k = 3
Path: 0 → 3 → 4 (cost: 4 + 3 + 2 = 9)
Output: 9
অ্যালগরিদম: Monotonic Queue / Sliding Window Minimum (DP Optimization)
নামিনেট DP: dp[i] = stairs[i] + min(dp[i-k], ..., dp[i-1])। এই স্লাইডিং উইন্ডো মিনিমাম Deque (Double-ended Queue) দিয়ে O(1) আমর্টাইজড এ করা যায়।
পাইথন কোড
from collections import deque
class Solution:
def solve(self, stairs, k):
# Deque stores (cost, index) pairs, increasing cost order
q = deque([(stairs[0], 0)])
for i in range(1, len(stairs)):
# উইন্ডোর বাইরে থাকলে পপ (i - q[0][1] > k)
while i - q[0][1] > k:
q.popleft()
# বেস্ট প্রিভিয়াস কোস্ট + করেন্ট স্টেয়ার কোস্ট
cur_cost = q[0][0] + stairs[i]
# Monotonicity মেইনটেইন: বড় কোস্ট वाले পপ
while q and cur_cost <= q[-1][0]:
q.pop()
q.append((cur_cost, i))
# লাস্ট এলিমেন্টের কোস্ট = আন্সার
return q[-1][0]
ob = Solution()
stairs = [4, 11, 11, 3, 2]
k = 3
print(ob.solve(stairs, k)) # 9
Deque ইনভেরিয়ান্ট
- Front: স্লাইডিং উইন্ডোর মিনিমাম কোস্ট
- Increasing order: কোস্ট বর্ধমান ক্রমে (ফ্রন্টে মিন)
- Index range: [i-k, i-1] উইন্ডো মেইনটেইন
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(n) — প্রতিটি এলিমেন্ট একবার পুশ/পপ
- স্থান জটিলতা: O(k) — ডিক সাইজ ≤ k
- নormais DP O(n×k) → Monotonic Queue O(n)
সাধারণ DP (তুলনার জন্য)
def solve_dp(stairs, k):
n = len(stairs)
dp = [float('inf')] * n
dp[0] = stairs[0]
for i in range(1, n):
for j in range(max(0, i-k), i):
dp[i] = min(dp[i], dp[j] + stairs[i])
return dp[-1]
উপসংহার
- Monotonic Queue / Sliding Window Minimum — DP অপ্টিমাইজেশনের ক্লাসিক প্যাটার্ন
collections.dequeব্যবহার করে O(1) আমর্টাইজড- স্টক স্প্যান, স্লাইডিং উইন্ডো ম্যাক্স/মিন, DP অপ্টিমাইজেশনে প্রয়োগ
