Giả sử chúng ta có một danh sách các số dương được gọi là nums. Bây giờ hãy xem xét một phép toán trong đó chúng ta loại bỏ bất kỳ hai giá trị a và b nào trong đó a ≤ b và nếu a
Vì vậy, nếu đầu vào giống như nums =[2, 4, 5], thì đầu ra sẽ là 1, bởi vì, chúng ta có thể chọn 4 và 5 sau đó chèn trở lại 1 để nhận được [2, 1]. Bây giờ, hãy chọn 2 và 1 để nhận [1].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- s:=tổng của tất cả các phần tử có trong nums
- Định nghĩa một hàm f (). Điều này sẽ khiến tôi mất
- if i> =size of nums, then
- trả lại s
- n:=nums [i]
- nếu s - 2 * n <0, thì
- return f (i + 1, s)
- trả về giá trị tối thiểu f (i + 1, s - 2 * n) và f (i + 1, s)
- từ phương thức chính trả về f (0, s)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(nums): s = sum(nums) def f(i, s): if i >= len(nums): return s n = nums[i] if s - 2 * n < 0: return f(i + 1, s) return min(f(i + 1, s - 2 * n), f(i + 1, s)) return f(0, s) nums = [2, 4, 5] print(solve(nums))
Đầu vào
[2, 4, 5]
Đầu ra
1