Giả sử chúng ta có một danh sách các số được gọi là nums và chúng được sắp xếp theo thứ tự tăng dần, chúng ta phải xóa k giá trị khỏi danh sách sao cho chênh lệch lớn nhất giữa hai giá trị liền kề là nhỏ nhất có thể, và cuối cùng tìm sự khác biệt.
Vì vậy, nếu đầu vào giống như nums =[15, 20, 30, 400, 1500] k =2, thì đầu ra sẽ là 10, như thể chúng ta loại bỏ [400, 1500] để nhận được sự khác biệt là 20 và 30.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- abs_diff:=danh sách các điểm khác biệt của mọi phần tử liên tiếp theo nums
- Định nghĩa một hàm dp (). Điều này sẽ mất i, j, cnt
- nếu cnt giống 0, thì
- m:=0
- đối với k trong phạm vi từ i đến j, thực hiện
- m:=tối đa là m và abs_diff [k]
- trả lại m
- trả về giá trị tối thiểu của dp (i + 1, j, cnt - 1) và dp (i, j - 1, cnt - 1)
- Từ phương thức chính, hãy làm như sau:
- return dp (0, kích thước của abs_diff - 1, k)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, nums, k): abs_diff = [nums[i] - nums[i - 1] for i in range(1, len(nums))] def dp(i, j, cnt): if cnt == 0: m = 0 for k in range(i, j + 1): m = max(m, abs_diff[k]) return m return min(dp(i + 1, j, cnt - 1), dp(i, j - 1, cnt - 1)) return dp(0, len(abs_diff) - 1, k) ob = Solution() nums = [15, 20, 30, 400, 1500] k = 2 print(ob.solve(nums, k))
Đầu vào
[15, 20, 30, 400, 1500], 2
Đầu ra
10