Giả sử chúng ta có một mảng các số dương; chúng ta thay thế từng phần tử từ mảng mảng đó để sự khác biệt giữa hai phần tử liền kề trong mảng nhỏ hơn hoặc bằng một mục tiêu đã cho. Bây giờ, chúng ta phải giảm thiểu chi phí điều chỉnh, vì vậy tổng chênh lệch giữa giá trị mới và giá trị cũ. Chính xác hơn, chúng tôi giảm thiểu ∑ | A [i] - Anew [i] | trong đó i trong phạm vi từ 0 đến n-1, ở đây n được biểu thị là kích thước của A và Anew là mảng có hiệu số liền kề nhỏ hơn hoặc bằng mục tiêu.
Vì vậy, nếu đầu vào là [56, 78, 53, 62, 40, 7, 26, 61, 50, 48], target =20, thì đầu ra sẽ là 25
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của arr
-
bảng:=[[0 cho tôi trong phạm vi 0 đến M + 1] cho tôi trong phạm vi 0 đến n]
-
đối với j trong phạm vi 0 đến M + 1, thực hiện
-
bảng [0, j]:=| j - arr [0] |
-
-
đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện
-
đối với j trong phạm vi 0 đến M + 1, thực hiện
-
bảng [i, j]:=100000000
-
đối với k trong phạm vi tối đa là (j-target và 0) và tối thiểu là (M và j + target), thực hiện
-
table [i, j] =tối thiểu của table [i, j], table [i - 1, k] + | arr [i] - j |
-
-
-
-
ans:=10000000
-
đối với j trong phạm vi 0 đến M + 1, thực hiện
-
ans =tối thiểu của ans và bảng [n-1, j]
-
trả lại ans
-
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[56, 78, 53, 62, 40, 7, 26, 61, 50, 48], 20
Đầu ra
35