파이썬에서 연속적인 3개의 요소에서 적어도 하나의 요소를 취하여 최소합 부분수열을 찾는 프로그램

<시간/>

nums라고 하는 숫자 목록이 있다고 가정하고 주어진 목록에서 최소 합 하위 시퀀스를 찾아야 하므로 세 개의 연속 숫자로 구성된 모든 그룹에 대해 하나 이상의 숫자가 선택됩니다. 주어진 목록의 길이가 3보다 작은 경우에도 숫자를 선택해야 합니다.

따라서 입력이 nums =[2, 3, 4, 5, 6, 7]과 같으면 2와 5를 선택할 수 있으므로 출력은 7이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

n :=숫자 크기
n이 0과 같으면
- 0을 반환
n이 1과 같으면
- 반환 번호[0]
n이 2와 같으면
- nums[0] 및 nums[1]의 최소값 반환
table :=크기가 n이고 0으로 채워진 목록
테이블[0] :=숫자[0]
테이블[1] :=숫자[1]
테이블[2] :=숫자[2]
3에서 n 사이의 i에 대해 다음을 수행합니다.
- table[i] :=nums[i] + table[i - 3], table[i - 2] 및 table[i - 1]의 최소값
res :=table[n - 1], table[n - 2] 및 table[n - 3]의 최소값
반환 결과

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시 코드

class Solution:
   def solve(self, nums):
      n = len(nums)
      if n == 0:
         return 0
      if n == 1:
         return nums[0]
      if n == 2:
         return min(nums[0], nums[1])
      table = [0] * n

      table[0] = nums[0]
      table[1] = nums[1]
      table[2] = nums[2]

      for i in range(3, n):
         table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

         res = min(table[n - 1], table[n - 2], table[n - 3])
      return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

입력

[2, 3, 4, 5, 6, 7]