[LintCode] Minimum Adjustment Cost [Undone]

Aomine 发布于2019-08-14 15:29 / 2782人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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