สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาขนาดของลำดับการเพิ่มขึ้นที่ยาวที่สุดโดยมีองค์ประกอบคี่อย่างน้อย k
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[12, 14, 16, 5, 7, 8] k =2 ผลลัพธ์จะเป็น 3 เนื่องจากลำดับการเพิ่มขึ้นที่ยาวที่สุดโดยมีค่าคี่อย่างน้อย 2 ค่าคือ [5, 7, 8].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ดีที่สุด :=0
-
กำหนดฟังก์ชัน dp() นี่จะใช้เวลา i, j, คี่, ถ่าย
-
ถ้าคี่>=k แล้ว
-
ดีที่สุด :=สูงสุดและดีที่สุด
-
-
ถ้า j เท่ากับขนาดของ nums แล้ว
-
กลับ
-
-
ถ้า nums[j]> nums[i] แล้ว
-
dp(j, j + 1, คี่ +(nums[j] AND 1) ถ่ายแล้ว + 1)
-
-
dp(i, j + 1, คี่, ถ่ายแล้ว)
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
สำหรับฉันในช่วง 0 ถึงขนาดของ nums ทำ
-
dp(i, i + 1, nums[i] AND 1, 1)
-
-
ผลตอบแทนดีที่สุด
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
[12, 14, 16, 5, 7, 8], 2
ผลลัพธ์
3
