If the array before adjustment is A, the array after adjustment is B, you should minimize the sum of |A[i]-B[i]|
You can assume each number in the array is a positive integer and not greater than 100.
Example 1: Input: [1,4,2,3], target=1 Output: 2 Example 2: Input: [3,5,4,7], target=2 Output: 1
思路：f[i][k] 表示第i个数变成k时，前i个数调整的代价和最小值。
枚举第i-1个数调整成的数字j，再枚举第i个数调整成k.做转移。
public class Solution {
/**
* @param A: An integer array.
* @param target: An integer.
*/
public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
// write your code here
int n = A.size();
int[][] f = new int[n + 1][101];
for (int i = 0; i <= n ; ++i)
for (int j = 0; j <=100; ++j)
f[i][j] = Integer.MAX_VALUE;
for (int i = 0; i <= 100; ++i)
f[0][i] = 0;
for (int i = 1; i <=n; ++i)
for (int j = 0; j <= 100;++j)
if (f[i-1][j] != Integer.MAX_VALUE)
for (int k = 0; k <= 100; ++k)
if (Math.abs(j-k) <= target)
if (f[i][k] > f[i-1][j] + Math.abs(A.get(i-1)-k))
f[i][k] = f[i-1][j] + Math.abs(A.get(i-1)-k);
int ans = Integer.MAX_VALUE;
for (int i = 0; i <= 100; ++i)
if (f[n][i] < ans)
ans = f[n][i];
return ans;
}
}
原文：https://www.cnblogs.com/FLAGyuri/p/12078447.html