양수 배열이 있다고 가정합니다. 배열의 인접한 두 요소 간의 차이가 지정된 대상보다 작거나 같도록 해당 배열 배열의 각 요소를 교체합니다. 이제 조정 비용을 최소화하여 새 값과 이전 값의 차이의 합을 최소화해야 합니다. 보다 정확하게는 ∑|A[i] – Anew[i]|를 최소화합니다. 여기서 i는 0에서 n-1 사이의 범위에서, 여기서 n은 A의 크기로 표시되고 Anew는 인접 차이가 target보다 작거나 같은 배열입니다.
따라서 입력이 [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target =20인 경우 출력은 25
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=arr의 크기
-
table :=[[0 ~ M + 1 범위의 i에 대해 0] 0 ~ n 범위의 i에 대해]
-
0에서 M + 1 범위의 j에 대해 수행
-
테이블[0, j] :=|j - arr[0]|
-
-
범위 1에서 n까지의 i에 대해 수행
-
0에서 M + 1 범위의 j에 대해 수행
-
테이블[i, j] :=100000000
-
(j-target 및 0) 범위의 최대값 및 (M 및 j + target)의 최소값 범위에 있는 k에 대해
-
table[i,j] =table[i,j]의 최소값, table[i - 1,k] + |arr[i] - j|
-
-
-
-
답변 :=10000000
-
0에서 M + 1 범위의 j에 대해 수행
-
as =ans 및 table[n-1, j]
의 최소값 -
반환
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
M = 100 def get_min_cost(arr, target): n = len(arr) table = [[0 for i in range(M + 1)] for i in range(n)] for j in range(M + 1): table[0][j] = abs(j - arr[0]) for i in range(1, n): for j in range(M + 1): table[i][j] = 100000000 for k in range(max(j - target, 0), min(M, j + target) + 1): table[i][j] = min(table[i][j], table[i - 1][k] + abs(arr[i] - j)) ans = 10000000 for j in range(M + 1): ans = min(ans, table[n - 1][j]) return ans arr= [56, 78, 53, 62, 40, 7, 26, 61, 50, 48] target = 20 print(get_min_cost(arr, target))
입력
[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], 20
출력
35