หา Minimum Adjustment Cost ของอาร์เรย์ใน C++

แนวคิด

กำหนดอาร์เรย์จำนวนเต็มบวก ต้องปรับค่าแต่ละอิลิเมนต์ ให้ความต่างระหว่างโหนดติดกัน ≤ target เป้าหมาย: ลด Adjustment Cost ให้น้อยที่สุด ซึ่งนิยามว่า Σ|A[i] – A_new[i]| สำหรับทุก i (0 ≤ i ≤ n-1) สมมติค่าทุกตัว < M = 100

ตัวอย่าง

Input: arr = [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target = 20
Output: Minimum adjustment cost is 35

แนวทาง: Dynamic Programming

กำหนด dp[i][j] = adjustment cost ต่ำสุดเมื่อเปลี่ยน A[i] เป็น j

สมการ DP: dp[i][j] = min{dp[i-1][k]} + |j - A[i]| สำหรับทุก k ที่ |k - j| ≤ target

เงื่อนไข: max(j-target, 0) ≤ k ≤ min(M, j+target)

คำตอบสุดท้าย: min{dp[n-1][j]} สำหรับ 0 ≤ j ≤ M

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

#define M1 100

int minAdjustmentCost(int A1[], int n1, int target1) {
    int dp1[n1][M1 + 1];
    
    // จัดการอิลิเมนต์แรกแยก
    for (int j = 0; j <= M1; j++)
        dp1[0][j] = abs(j - A1[0]);
    
    // อิลิเมนต์ที่เหลือ
    for (int i = 1; i < n1; i++) {
        for (int j = 0; j <= M1; j++) {
            dp1[i][j] = INT_MAX;
            for (int k = max(j - target1, 0); k <= min(M1, j + target1); k++)
                dp1[i][j] = min(dp1[i][j], dp1[i-1][k] + abs(A1[i] - j));
        }
    }
    
    int res1 = INT_MAX;
    for (int j = 0; j <= M1; j++)
        res1 = min(res1, dp1[n1-1][j]);
    
    return res1;
}

int main() {
    int arr1[] = {56, 78, 53, 62, 40, 7, 26, 61, 50, 48};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int target1 = 20;
    cout << "Minimum adjustment cost is " << minAdjustmentCost(arr1, n1, target1) << endl;
    return 0;
}

ผลลัพธ์

Minimum adjustment cost is 35

Complexity: Time O(n × M × target), Space O(n × M) โดย M=100 สามารถลด Space เป็น O(M) ได้ด้วย rolling array