Tìm chi phí điều chỉnh tối thiểu của mảng trong Python

Cho mảng số dương, thay thế từng phần tử sao cho hiệu giữa hai phần tử liền kề ≤ target. Tối thiểu hóa chi phí điều chỉnh: tổng |A[i] - Anew[i]|.

Ví dụ: [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20 → Kết quả: 35 (lưu ý: output mẫu là 35).

Thuật toán Dynamic Programming

1. M = 100 (giá trị tối đa có thể của phần tử).
2. table[i][j] = chi phí tối thiểu cho tiền tố độ dài i+1 kết thúc bằng giá trị j.
3. Khởi tạo: table[0][j] = |j - arr[0]|.
4. Quy hoạch: table[i][j] = min(table[i-1][k] + |arr[i] - j|) với k ∈ [max(j-target, 0), min(M, j+target)].
5. Kết quả = min(table[n-1][j]) cho mọi j.

Ví dụ code

M = 100

def get_min_cost(arr, target):
    n = len(arr)
    table = [[0] * (M + 1) for _ in range(n)]
    for j in range(M + 1):
        table[0][j] = abs(j - arr[0])
    for i in range(1, n):
        for j in range(M + 1):
            table[i][j] = 100000000
            for k in range(max(j - target, 0), min(M, j + target) + 1):
                table[i][j] = min(table[i][j], table[i - 1][k] + abs(arr[i] - j))
    ans = 10000000
    for j in range(M + 1):
        ans = min(ans, table[n - 1][j])
    return ans

arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48]
target = 20
print(get_min_cost(arr, target))

Input

[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], 20

Output

35