양수 목록이 제공된다고 가정합니다. 이제 여기에서 동일한 값을 가진 길이 t의 인접한 하위 목록을 제거하고 포인트 t * t를 얻을 수 있습니다. 한 가지 조건은 목록이 비어 있을 때까지 여러 번 수행할 수 있다는 것입니다. 따라서 얻을 수 있는 최대 점수를 결정해야 합니다.
따라서 입력이 nums =[4, 4, 6, 4, 4]와 같으면 출력은 17이 됩니다.
출력을 위해 먼저 길이가 1이고 1 * 1 =1 포인트를 산출하는 6을 제거할 수 있습니다. 그런 다음 길이가 4이고 4 * 4 =16포인트를 생성하는 목록 [4, 4, 4, 4]를 사용할 수 있습니다. 그래서 마침내 우리는 17점을 얻을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dp() 함수를 정의합니다. 왼쪽, 오른쪽, t
-
왼쪽> 오른쪽이 0이 아니면
-
0 반환
-
-
숫자 :=숫자[왼쪽]
-
left2 :=왼쪽
-
동안 left2
-
left2 :=left2 + 1
-
-
t :=t + 왼쪽2 − 왼쪽 + 1
-
왼쪽 :=왼쪽2 + 1
-
포인트 :=t의 거듭제곱 2 + dp(left, right, 0)
-
중간 범위 왼쪽에서 오른쪽 + 1의 경우 수행
-
nums[mid]가 num과 같으면
-
Points :=(points, dp(left, mid − 1, 0) + dp(mid, right, t))
의 최대값
-
-
-
반환 포인트
-
주요 기능에서 우리는 다음을 수행합니다 -
-
print(dp(0, 숫자의 크기 - 1, 0))
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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]))
입력
[4, 4, 6, 4, 4]
출력
17