Minimum Adjustment Cost

Description

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.

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.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    // --------------------------------------------------------------
    // Version 1, O(n^2) s(n^2)
    int backPack(int m, vector<int> nums) {
        // write your code here
        if (nums.empty() || m <= 0) {
            return 0;
        }
        int len = nums.size();
        vector<vector<bool>> dp(len + 1, vector<bool>(m + 1, false));
        dp[0][0] = true;
        for (int i = 0; i < len; ++i) {
            for (int j = 0; j < m + 1; ++j) {
                dp[i+1][j] = dp[i][j];
                // make sure: cur j > nums[i] 
                // and [j-nums[i]] can be selected, so we can validate [j]
                if (j >= nums[i] && dp[i][j-nums[i]]) {
                    dp[i+1][j] = true;
                }
            }
        }
        for (int i = m; i >= 0; --i) {
            if (dp[len][i]) {
                return i;
            }
        }
        return 0;
    }
    // ----------------------------------------------------------------
    // Version 2, O(n^2) s(n)
    // reuse the dp[] array
    int backPack(int m, vector<int> nums) {
        // write your code here
        if (nums.empty() || m <= 0) {
            return 0;
        }
        int len = nums.size();
        // reused array
        vector<bool> dp(m + 1, false);
        dp[0] = true;
        for (int i = 0; i < len; ++i) {
            for (int j = m; j >= nums[i]; --j) {
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        for (int i = m; i >= 0; --i) {
            if (dp[i]) {
                return i;
            }
        }
        return 0;
    }
    // ----------------------------------------------------------------
};

Similar problems

x

Tags

x