nums라는 숫자 목록이 있다고 가정합니다. 이제 두 개의 연속 값을 취하여 합을 취하여 하나의 값으로 병합하는 작업을 고려해 보겠습니다. 목록이 증가하지 않도록 하려면 필요한 최소 연산 수를 찾아야 합니다.
따라서 입력이 nums =[2, 6, 4, 10, 2]와 같으면 출력은 2가 됩니다. [2, 6]을 병합하여 [8, 4, 10, 2]를 얻은 다음 [8, 4]를 병합하여 [12, 10, 2]를 얻습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
숫자가 비어 있으면
-
0 반환
-
-
숫자 끝에 -inf 삽입
-
N :=숫자 크기
-
dp :=크기가 N이고 0으로 채워진 목록
-
arr :=크기가 N이고 0으로 채워진 목록
-
p :=arr의 크기
-
arr[p−1] :=숫자[N−1]
-
arr[p−2] :=숫자[N−2]
-
범위 N - 3에서 0의 i에 대해 1만큼 감소, 수행
-
j :=나는
-
x :=숫자[j]
-
j
-
j :=j + 1
-
x :=x + 숫자[j]
-
-
dp[i] :=j − i + dp[j + 1]
-
arr[i] :=x
-
-
반환 dp[0]
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution:
def solve(self, nums):
if not nums:
return 0
nums.append(float("−inf"))
N = len(nums)
dp = [0] * N
arr = [0] * N
arr[−1] = nums[−1]
arr[−2] = nums[−2]
for i in range(N − 3, −1, −1):
j = i
x = nums[j]
while j < N − 1 and x < arr[j + 1]:
j += 1
x += nums[j]
dp[i] = j − i + dp[j + 1]
arr[i] = x
return dp[0]
ob = Solution()
nums = [2, 6, 4, 10, 2]
print(ob.solve(nums)) 입력
[2, 6, 4, 10, 2]
출력
2