91.Minimum Adjustment Cost-最小调整代价（中等题）

本文主要是介绍91.Minimum Adjustment Cost-最小调整代价（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最小调整代价

1. 题目

   给一个整数数组，调整每个数的大小，使得相邻的两个数的差小于一个给定的整数target，调整每个数的代价为调整前后的差的绝对值，求调整代价之和最小是多少。

   注意事项
   你可以假设数组中每个整数都是正整数，且小于等于100。

2. 样例

   对于数组[1, 4, 2, 3]和target=1，最小的调整方案是调整为[2, 3, 2, 3]，调整代价之和是2。返回2。

3. 题解

public class Solution {/*** @param A: An integer array.* @param target: An integer.*/public int MinAdjustmentCost(ArrayList<Integer> A, int target) {int n = A.size();int[][] f = new int[n + 1][101];for (int i = 1; i <= n ; ++i){for (int j = 0; j <=100; ++j){f[i][j] = Integer.MAX_VALUE;}}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 result = Integer.MAX_VALUE;for (int i = 0; i <= 100; ++i){result = Math.min(result,f[n][i]);}return result; }
}

Last Update 2016.10.7

这篇关于91.Minimum Adjustment Cost-最小调整代价（中等题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---