【算法题】minimum-adjustment-cost

梦里梦外; 2022-06-04 06:48 141阅读 0赞

题目描述：

Given an integer array, adjust each integers so that the difference of every adjacent integers are not greater than a given number target.

If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of `|A[i]-B[i]|`

#####  Notice #####

You can assume each number in the array is a positive integer and not greater than `100`.

Have you met this question in a real interview?

Yes

Example

Given `[1,4,2,3]` and target = `1`, one of the solutions is `[2,3,2,3]`, the adjustment cost is `2` and it's minimal.

Return `2`.

题目连接：

http://www.lintcode.com/en/problem/minimum-adjustment-cost/

中文描述：给一个整数数组，调整每个数的大小，使得相邻的两个数的差不大于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

思路：

这个是动态规划背包问题。

state: dp\[i\]\[j\] 到A\[i\]为止A\[i\]变为j的时候的min cost

initalization:dp\[0\]\[j\] = abs(A\[0\] - j)

function:dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i - 1\]\[j\] + A\[i\] - j)

result:min(dp\[A.size - 1\]\[j\])

这个其实需要三层循环，第三层循环的时候用到target这个值，根据j和target确定这次的j的范围。并且取最小的那个情况。

这个题目的标准思路和状态及方程是上面这样，我的优化思路： j的取值范围是从A中的最小值到最大值的 ，所以没必要从0到100循环。也就是他提示的假设条件是不需要的。

此时状态方程需要稍稍调整，直接贴出我的代码。

class Solution {
    public:
        /*
         * @param A: An integer array
         * @param target: An integer
         * @return: An integer
         */
        int MinAdjustmentCost(vector<int> &A, int target) {
            int max_a = *(max_element(A.begin(), A.end()));
            int min_a = *(min_element(A.begin(), A.end()));
            vector<vector<int>> dp(A.size(), vector<int>(101, INT_MAX));
            for (int i = 0; i <= max_a - min_a; i++) {
                dp[0][i] = abs(A[0] - (i + min_a));
            }
            for (int i = 1; i < A.size(); i++) {
                for (int j = 0; j <= max_a - min_a; j++) {
                    for (int k = max(min_a, j + min_a - target); k <= min(max_a, j + min_a + target); k++) {
                        dp[i][j] = min(dp[i][j], dp[i - 1][k - min_a] + abs(A[i] - (j + min_a)));
                    }
                }
            }
            return *(min_element(dp[A.size() - 1].begin(), dp[A.size() - 1].end()));
        }
    };