Giả sử chúng ta được cung cấp một danh sách các số dương. Bây giờ, ở đây chúng ta có thể xóa bất kỳ danh sách con liền kề nào có độ dài t có cùng giá trị và nhận điểm t * t. Một điều kiện cần được xem xét, đó là chúng ta có thể thực hiện điều này bất kỳ số lần nào cho đến khi danh sách trống. Vì vậy, chúng tôi phải xác định số điểm tối đa mà chúng tôi có thể nhận được.
Vì vậy, nếu đầu vào là nums =[4, 4, 6, 4, 4], thì đầu ra sẽ là 17.
Đối với đầu ra, trước tiên chúng ta có thể loại bỏ số 6 có độ dài 1 và thu được 1 * 1 =1 điểm. Sau đó, chúng ta có thể lấy danh sách [4, 4, 4, 4] có độ dài 4 và thu được 4 * 4 =16 điểm. Vì vậy, cuối cùng, chúng tôi có thể nhận được 17 điểm.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dp (). Thao tác này sẽ chuyển sang trái, phải, t
-
nếu left> right là khác 0, thì
-
trả về 0
-
-
num:=nums [left]
-
left2:=left
-
trong khi left2
-
left2:=left2 + 1
-
-
t:=t + left2 - left + 1
-
left:=left2 + 1
-
điểm:=t thành lũy thừa 2 + dp (trái, phải, 0)
-
cho giữa trong phạm vi từ trái sang phải + 1, thực hiện
-
nếu nums [mid] giống num thì
-
điểm:=tối đa của (điểm, dp (trái, giữa - 1, 0) + dp (giữa, phải, t))
-
-
-
trả lại điểm
-
Từ chức năng chính, chúng tôi thực hiện như sau -
-
print (dp (0, kích thước của nums - 1, 0))
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): def dp(left, right, t): if left > right: return 0 num = nums[left] left2 = left while left2 < right and nums[left2 + 1] == num: left2 += 1 t += left2 − left + 1 left = left2 + 1 points = t ** 2 + dp(left, right, 0) for mid in range(left, right + 1): if nums[mid] == num: points = max(points, dp(left, mid − 1, 0) + dp(mid, right, t)) return points return dp(0, len(nums) − 1, 0) ob1 = Solution() print(ob1.solve([4, 4, 6, 4, 4]))
Đầu vào
[4, 4, 6, 4, 4]
Đầu ra
17