算法面試真題詳解：最小調整代價

給一個整數數組，調整每個數的大小，使得相鄰的兩個數的差不大于一個給定的整數target，調整每個數的代價為調整前後的差的絕對值，求調整代價之和最小是多少。

你可以假設數組中每個整數都是正整數，且小于等于100。

線上評測位址：

領扣題庫官網

樣例1：
輸入:  [1,4,2,3], target=1
  輸出:  2           

樣例2：
輸入:  [3,5,4,7], target=2
        輸出:  1           

算法：dp

思路

已知每個整數範圍[1,100]，那麼對于每個元素，為了調整到該元素和與之相鄰的元素的差不大于target，該元素調整的範圍就在[1,100]。是以對于數組A[]的每一位元素，我們都需要進行[1,100]範圍内的可能狀态的轉移。

令dpi表示元素A[i]=j時，A[i]與A[i-1]內插補點不大于target所需要付出的最小代價。

當A[i]=j時，可行的A[i-1]的範圍為[max(1, j - target)，min(100, j + target)]。而dpi為所有可行的A[i-1]中，花費代價最小的一種可能，再加上A[i]調整到 j 所需花費abs(j - A[i])。

當A[i]=j時，k在[max(1, j - target)，min(100, j + target)]範圍内時，我們可以寫出以下式子：

1.臨界值：

dp0 = abs(j - A[0])

2.狀态轉移方程：

dpi = min(dpi, dpi - 1 + abs(j - A[i]))

最後在所有最後一位的可能解dpn-1中的最小值，就是我們所求的最小代價。

複雜度

假設數組長度為n

空間複雜度O(10000*n)

時間複雜度O(n^2)

題解：

public class Solution {
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    public int MinAdjustmentCost(List<Integer> A, int target) {
        int n = A.size();
        // dp[i][j]表示元素A[i]=j時，A[i]與A[i-1]內插補點不大于target所需要付出的最小代價
        int[][] dp = new int[n][101];
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 100; j++) {
                // 初始化為極大值
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= 100; j++) {
                if (i == 0) {
                    // 臨界值：第一個元素A[0]調整為j的代價 
                    dp[0][j] = Math.abs(j - A.get(0));
                }
                else {
                    // left為A[i]=j時，A[i-1]與A[i]內插補點不大于target的A[i-1]最小值
                    // right為A[i]=j時，A[i-1]與A[i]內插補點不大于target的A[i-1]最大值
                    int left = Math.max(1, j - target);  
                    int right = Math.min(100, j + target);  
                    for (int k = left; k <= right; k++) {
                        // 當A[i-1]=k時，答案為A[i-1]=k的代價dp[i-1][k]，加上A[i]=j的調整代價abs(j-A[i])
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + Math.abs(j - A.get(i))); 
                    }
                }
                
            }
        }
        int mincost = Integer.MAX_VALUE;
        for (int i = 1; i <= 100; i++) {
            mincost = Math.min(mincost, dp[n - 1][i]);
        }
        return mincost;
    }
}           

更多題解參考：

九章官網solution