91-最小調整コスト
91 Minimum Adjustment Cost
-
説明
整数配列の場合、隣接する2つの数値の差が特定の整数ターゲットを超えないように各数値のサイズを調整し、各数値の調整コストは調整の前後になります。差の絶対値は最小です。調整費用の合計。 -
予防
配列内の各整数は正の整数であり、100以下であると想定できます。
-
サンプル
配列[1、4、2、3]およびtarget = 1の場合、最小調整スキームは[2、3、2、3]に調整することであり、調整コストの合計は2です。2を返します。 -
ラベル
動的計画バックパック問題LintCodeAll rights reserved
ソリューション
配列A内の任意の数値について、2つの数値の差が調整後の目標を超えない限り、自由に調整できます。
状態：
動的計画法が使用される場合、状態f（i）（j）はjに変換されるi番目の数を表す可能性が高く、iが隣接するものとの差に達する前のすべての数はターゲットより大きくありません。最小コスト。
状態転送：f（i）（j）= m i n（f（i − 1）（x）+ ∣ j − A [i] ∣ ∣ j − x ∣<= t a r g e t f(i)(j) = min( f(i-1)(x) + |j - A[i]| |j-x| <= target
f（i）（j）の最小コストは、i-1の数値をxに変換する最小コスト（xとjの差がターゲットよりも小さいことを保証する）にA [i]変換を加えたものに等しくなります。 jの
初期値：
f（i）（0）= A [i]：A [i]を0に変換するための最小コストはA [i]に等しくなります。
f（1）（j）：A [0]を0に変換するコストは、| j-A [0] |に等しくなります。 f（0）（j）が0に設定されている場合、F（1）（j）= min（f（0）（x）+ | j-A [i] | = | j-A [0] |
回答：
m i n f（n）（x）0<= x < = 100 min f(n)(x) 0<=x <= 100
C ++コード
class Solution { public: int minAdjustCost(vector<int> A,int target) { if (A.empty() || target >= 100) return 0 vector<vector<int>> dp(A.size() + 1, vector<int>(101, 0)) for (int i = 1 i <= A.size() i++) { dp[i][0] = A[i-1] for (int j = 1 j<=100j ++) { int subStart = std::max(0, j - target ) int subEnd = std::min(100, j + target ) int subMinCost = 100 for (int x = subStart x < subEnd x++) if (dp[i - 1][x] < subMinCost) subMinCost = dp[i - 1][x] dp[i][j] = subMinCost + std::abs(j - A[i - 1]) } } int minCost = 100 for (int i = 0 i <= 100 i++) if (dp[A.size()][i] < minCost) minCost = dp[A.size()][i] return minCost } } int main() { Solution so vector<int> arr = { 1,4,2,3 } int ret = so.minAdjustCost(arr, 1) cout << ret << endl system('pause') return 0 }