ข้อ 60 · LC746 Min Cost Climbing Stairs (ขึ้นบันไดถูกสุด) 🟢

โจทย์ (LC746): กำหนด array จำนวนเต็ม cost มา โดย cost[i] คือค่าใช้จ่ายของขั้นบันไดที่ i เมื่อจ่ายค่าใช้จ่ายของขั้นนั้นแล้ว สามารถก้าวขึ้นได้ 1 หรือ 2 ขั้น สามารถเริ่มต้นได้จากขั้นที่ index 0 หรือ index 1 ก็ได้ ให้หาค่าใช้จ่าย minimum ที่จะไปให้ถึงยอดบันได (จุดที่พ้นขั้นสุดท้าย)

แนวทาง — ต้องใช้อะไร & คิดยังไง

นี่คือ DP 1 มิติ pattern เดียวกับ Fibonacci เป๊ะ ต่างแค่ใช้ min แทนการ sum นิยาม dp[i] = cost น้อยสุดที่จะมาถึงขั้น i ก่อนเหยียบ การจะถึงขั้น i ได้ ต้อง jump (กระโดด) มาจากขั้น i-1 (จ่าย cost[i-1]) หรือขั้น i-2 (จ่าย cost[i-2]) เลือกทางที่ถูกกว่า

ประเด็นที่คนงงคือ cost อยู่ที่ตัวขั้น ไม่ใช่ที่การ step และเราจ่ายเมื่อออกจากขั้นนั้น การ define dp[i] เป็นค่าที่จะมาถึงขั้น i (ยังไม่เหยียบ i) ทำให้ transition สวย และเป้าหมายคือ dp[n] เมื่อ n คือ length ของ cost (จุดพ้นยอดซึ่งไม่มีค่า cost)

1. initialize dp ยาว n+1 โดย n = len(cost)
2. ตั้ง base case: dp[0] = dp[1] = 0 เพราะเริ่มที่ขั้น 0 หรือ 1 ได้ฟรี
3. iterate i จาก 2 ถึง n: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
4. return dp[n] ซึ่งคือจุดพ้นบันได

ไล่ทีละสเต็ป

ไล่ cost = [10,15,20] (n = 3):

def min_cost_climbing_stairs(cost):
    n = len(cost)
    dp = [0] * (n + 1)   # dp[i] = ค่าใช้จ่ายน้อยสุดเพื่อมาถึงขั้น i
    # dp[0] = dp[1] = 0 เพราะเริ่มที่ขั้น 0 หรือ 1 ได้ฟรี
    for i in range(2, n + 1):
        dp[i] = min(dp[i - 1] + cost[i - 1],   # มาจากขั้นก่อนหน้า
                    dp[i - 2] + cost[i - 2])   # มาจากขั้นก่อนสองขั้น
    return dp[n]

print(min_cost_climbing_stairs([10, 15, 20]))                # 15
print(min_cost_climbing_stairs([1,100,1,1,1,100,1,1,100,1])) # 6

15
6