[LintCode] Minimum Adjustment Cost [Undone]

Aomine 發布于2019-08-14 15:29 / 2825人閱讀

Problem

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.

Note Solution

public class Solution {
    public int MinAdjustmentCost(ArrayList A, int target) {
        int n = A.size(), res = Integer.MAX_VALUE, max = res;
        int[][] dp = new int[n][101];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 100; j++) {
                dp[i][j] = i == 0 ? Math.abs(j - A.get(i)) : max;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= 100; j++) {
                for (int k = j-target; k <= j+target && k <= 100; k++) {
                    if (k >= 0 && dp[i-1][k] < max) dp[i][j] = Math.min(dp[i][j], dp[i-1][k]+Math.abs(j-A.get(i)));
                }
            }
        }
        for (int j = 0; j <= 100; j++) {
            res = Math.min(res, dp[n-1][j]);
        }
        return res;
    }
}



    public int MinAdjustmentCost(ArrayList A, int target) {  
        int n = A.size();  
        int max = 0;  
        for (int i = 0; i < n; i++) {  
            max = Math.max(max, A.get(i));  
        }  
        int[][] d = new int[n][max+1];  
        for (int j = 0; j <= max; j++) {  
            d[0][j] = Math.abs(A.get(0) - j);  
        }  
        int curMin = 0;  
        for (int i = 1; i < n; i++) {  
            curMin = Integer.MAX_VALUE;  
            for (int j = 0; j <= max; j++) {  
                d[i][j] = Integer.MAX_VALUE;  
                for (int k = Math.max(0, j-target); k <= Math.min(max, j+target); k++) {  
                    d[i][j] = Math.min(d[i][j], d[i-1][k] + Math.abs(A.get(i)-j));  
                    curMin = Math.min(curMin, d[i][j]);  
                }  
            }  
        }  
        return curMin;  
    }  
}

云服務器 GPU云服務器 Undone Adjustment Cost Minimum

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65797.html

[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原數組上動規，每一行對應一個房子，每一個元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開銷。所以每個元素該元素的值上一行兩個與該元素不同列元素的值的較小者。不過這次要記錄三個變量本行最小值，本行第二小值，本行最小值下標。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 評論0 收藏0
[LintCode/LeetCode] Gas Station

摘要：看到這個題目，怎樣可以不把它當成一個環路來分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點四個參數。大體上說，只要，一定有解。所以跳過這個耗油量很大的油站，然后將下一個油站作為起點繼續判斷即可。 Problem There are N gas stations along a circular route, where the amount ...

hedge_hog 2019-08-14 15:21 評論0 收藏0
[LintCode] Minimum Absolute Difference in BST

Problem Minimum Absolute Difference in BSTGiven a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example Input: 1 3 ...

curlyCheng 2019-08-16 12:36 評論0 收藏0
[LintCode/LeetCode] Minimum Window Substring

Problem Given a string source and a string target, find the minimum window in source which will contain all the characters in target. Notice If there is no such window in source that covers all charac...

Corwien 2019-08-14 15:43 評論0 收藏0
[LintCode/LeetCode] Find Minimum in Rotated Sorted

摘要：排序數組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點和中點元素的大小關系即可。這里有一種情況是上述后三個，中點值和末位相等。此時，兩邊同時遞歸，并返回兩邊遞歸值的較小值。當首位和末位重合，說明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

cgh1999520 2019-08-14 15:22 評論0 收藏0