資訊專欄INFORMATION COLUMN
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]|
NoticeYou can assume each number in the array is a positive integer and not greater than 100.
ExampleGiven [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 Solutionpublic 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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/65797.html
摘要：在原數(shù)組上動(dòng)規(guī)，每一行對(duì)應(yīng)一個(gè)房子，每一個(gè)元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開(kāi)銷。所以每個(gè)元素該元素的值上一行兩個(gè)與該元素不同列元素的值的較小者。不過(guò)這次要記錄三個(gè)變量本行最小值，本行第二小值，本行最小值下標(biāo)。 Paint House Problem There are a row of n houses, each house can be painted ...
摘要：看到這個(gè)題目，怎樣可以不把它當(dāng)成一個(gè)環(huán)路來(lái)分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點(diǎn)四個(gè)參數(shù)。大體上說(shuō)，只要，一定有解。所以跳過(guò)這個(gè)耗油量很大的油站，然后將下一個(gè)油站作為起點(diǎn)繼續(xù)判斷即可。 Problem There are N gas stations along a circular route, where the amount ...
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 ...
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...
摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。這里有一種情況是上述后三個(gè)，中點(diǎn)值和末位相等。此時(shí)，兩邊同時(shí)遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說(shuō)明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...
閱讀 3885·2021-11-17 09:33
閱讀 1196·2021-10-09 09:44
閱讀 400·2019-08-30 13:59
閱讀 3478·2019-08-30 11:26
閱讀 2178·2019-08-29 16:56
閱讀 2849·2019-08-29 14:22
閱讀 3151·2019-08-29 12:11
閱讀 1269·2019-08-29 10:58
