โจทย์: กำหนดอาร์เรย์ A และ target ปรับค่าแต่ละตัวให้ผลต่างระหว่างติดกัน ≤ target ลดผลรวม |A[i] - Anew[i]| ให้น้อยที่สุด
ตัวอย่าง: A=[56,78,53,62,40,7,26,61,50,48], target=20 → output=35 (หมายเหตุ: ต้นฉบับเขียน 25 แต่โค้ดให้ 35)
อัลกอริทึม Dynamic Programming
DP[i][v] = ต้นทุนน้อยที่สุดสำหรับ prefix i ตัว โดย Anew[i] = v
Transition: DP[i][v] = min(DP[i-1][u] + |A[i] - v|) สำหรับ u ใน [max(0, v-target), min(M, v+target)]
M = 100 (ค่าสูงสุดที่เป็นไปได้ขององค์ประกอบ)
ตัวอย่างโค้ด
M = 100
def get_min_cost(arr, target):
n = len(arr)
dp = [[0] * (M + 1) for _ in range(n)]
# base case: i = 0
for v in range(M + 1):
dp[0][v] = abs(v - arr[0])
# fill DP table
for i in range(1, n):
for v in range(M + 1):
dp[i][v] = float('inf')
for u in range(max(v - target, 0), min(M, v + target) + 1):
dp[i][v] = min(dp[i][v], dp[i-1][u] + abs(arr[i] - v))
# answer = min over last row
return min(dp[n-1])
arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48]
target = 20
print(get_min_cost(arr, target)) # 35
ผลลัพธ์
35
สรุป: DP แบบ bottom-up O(n × M × target) ใช้ได้เพราะ M=100 เล็ก สามารถ optimize ด้วย sliding window minimum ได้
