Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải tìm kích thước của dãy con tăng dần dài nhất có ít nhất k phần tử lẻ.
Vì vậy, nếu đầu vào là nums =[12, 14, 16, 5, 7, 8] k =2, thì đầu ra sẽ là 3, vì dãy con tăng dần dài nhất có ít nhất 2 giá trị lẻ là [5, 7, 8].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
tốt nhất:=0
-
Định nghĩa một hàm dp (). Điều này sẽ lấy i, j, lẻ, lấy
-
nếu lẻ> =k thì
-
tốt nhất:=tối đa trong số tốt nhất và được thực hiện
-
-
nếu j giống với kích thước của nums, thì
-
trở lại
-
-
nếu nums [j]> nums [i], thì
-
dp (j, j + 1, lẻ + (nums [j] VÀ 1), lấy + 1)
-
-
dp (i, j + 1, lẻ, lấy)
-
Từ phương thức chính, hãy làm như sau -
-
đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
-
dp (i, i + 1, nums [i] AND 1, 1)
-
-
trở lại tốt nhất
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution: def solve(self, nums, k): best = 0 def dp(i, j, odd, taken): nonlocal best if odd >= k: best = max(best, taken) if j == len(nums): return if nums[j] > nums[i]: dp(j, j + 1, odd + (nums[j] & 1), taken + 1) dp(i, j + 1, odd, taken) for i in range(len(nums)): dp(i, i + 1, nums[i] & 1, 1) return best ob = Solution() nums = [12, 14, 16, 5, 7, 8] k = 2 print(ob.solve(nums, k))
Đầu vào
[12, 14, 16, 5, 7, 8], 2
Đầu ra
3