Giả sử chúng ta có một danh sách các số được gọi là num, chúng ta phải kiểm tra xem mọi số có thể được nhóm lại hay không bằng cách sử dụng một trong các quy tắc sau:1. Các cặp liền kề (a, a) 2. Các bộ ba liền kề (a, a, a) 3. Liền kề sinh ba (a, a + 1, a + 2)
Vì vậy, nếu đầu vào là nums =[7, 7, 3, 4, 5], thì đầu ra sẽ là True, vì Chúng ta có thể nhóm [7, 7] lại với nhau và [3, 4, 5] lại với nhau.
Để 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 nums
-
dp:=danh sách có kích thước n + 1, giá trị đầu tiên là Đúng, các giá trị khác là Sai
-
đối với tôi trong phạm vi từ 2 đến n, hãy làm
-
nếu i> =2 và dp [i - 2] không phải 0 thì
-
nếu nums [i - 1] giống nums [i - 2] thì
-
dp [i]:=Đúng
-
-
-
nếu i> =3 và dp [i - 3] không phải 0 thì
-
nếu (nums [i - 1], nums [i - 2], nums [i - 3]) giống nhau hoặc (nums [i - 1], nums [i - 2] + 1, nums [i - 3] + 2 giống nhau), sau đó
-
dp [i]:=Đúng
-
-
-
-
trả về dp [n]
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): n = len(nums) dp = [True] + [False] * n for i in range(2, n + 1): if i >= 2 and dp[i − 2]: if nums[i − 1] == nums[i − 2]: dp[i] = True if i >= 3 and dp[i − 3]: if (nums[i − 1] == nums[i − 2] == nums[i − 3]) or (nums[i − 1] == nums[i − 2] + 1 == nums[i − 3] + 2): dp[i] = True return dp[n] ob = Solution() nums = [8, 8, 4, 5, 6] print(ob.solve(nums))
Đầu vào
[8, 8, 4, 5, 6]
Đầu ra
True