Python Programming: Dynamic Programming

def fib_bottom_up(n):
    # 1. สร้างตาราง (List) ขนาด n+1 ช่อง (เริ่มด้วย 0 ทั้งหมด)
    dp = [0] * (n + 1)
    
    # 2. ใส่ค่า Base Case (ถ้า n น้อยกว่า 2 ให้ return n เลย)
    if n <= 1:
        return n
        
    dp[0] = 0
    dp[1] = 1
    
    # 3. วนลูปเติมค่าตั้งแต่ช่องที่ 2 จนถึง n
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # สูตรเดิม แต่ใช้ค่าจากตาราง
        
    return dp[n]  # คืนค่าช่องสุดท้าย

print(fib_bottom_up(100))  # เร็วมากและไม่ Error!

def coin_change(coins, amount):
    # สร้างตาราง และใส่ค่า Infinity ไว้ก่อนเพื่อหาตัวน้อยสุด
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    # วนลูปเงินตั้งแต่ 1 บาท ถึง amount
    for i in range(1, amount + 1):
        # ลองหยิบเหรียญแต่ละแบบ
        for coin in coins:
            if i - coin >= 0:  # เช็คว่าเงินพอให้หยิบเหรียญนี้ไหม
                # สูตร: min(ค่าเดิม, ค่าของเงินที่เหลือ + 1 เหรียญ)
                dp[i] = min(dp[i], dp[i - coin] + 1)
                
    # ถ้าค่าเป็น inf แปลว่าทอนไม่ได้ ให้ตอบ -1
    return dp[amount] if dp[amount] != float('inf') else -1

print(coin_change([1, 3, 4], 6))  # Output: 2

def grid_traveler(m, n):
    # 1. สร้างตาราง 2 มิติ ขนาด m x n (เติม 0 ไว้ก่อน)
    dp = [[0] * n for _ in range(m)]
    
    # 2. Base Case: แถวบนสุด และ คอลัมน์ซ้ายสุด มีค่าเป็น 1
    for r in range(m):
        dp[r][0] = 1
    for c in range(n):
        dp[0][c] = 1
        
    # 3. วนลูปเติมค่าข้างใน (เริ่มที่ r=1, c=1)
    for r in range(1, m):
        for c in range(1, n):
            # สูตร: บน + ซ้าย
            dp[r][c] = dp[r-1][c] + dp[r][c-1]
            
    # 4. คำตอบอยู่ที่มุมขวาล่างสุด
    return dp[m-1][n-1]

print(f"ตาราง 3x3 มีทางเดิน: {grid_traveler(3, 3)} วิธี")  # Output: 6