Python에서 곱셈 연산을 수행하여 최대 점수를 찾는 프로그램

<시간/>

각각 크기가 n과 m인 두 개의 배열 num과 승수가 있다고 가정합니다(n>=m). 배열은 1-인덱싱됩니다. 이제 초기 점수는 0입니다. 정확히 m개의 작업을 수행하려고 합니다. i번째 연산(1-인덱스)에서 우리는 -

숫자의 시작 또는 끝에서 x에서 하나의 값을 선택합니다.
점수에 승수[i] * x를 추가합니다.
배열 번호에서 x를 제거합니다.

m개의 연산을 수행한 후 최대 점수를 찾아야 합니다.

따라서 입력이 nums =[5,10,15], multipliers =[5,3,2]와 같으면 출력은 115가 됩니다. 왜냐하면 15를 취한 다음 5를 곱하여 5*15 =75를 얻을 수 있기 때문입니다. , 10*3 =30이므로 합계는 75+30 =105이고 마지막으로 5*2 =10이므로 합계는 105+10 =115입니다.

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

n :=숫자의 크기, m :=크기 승수
dp :=m x (m+1) 크기의 2D 배열 하나와 0으로 채움
목록 범위 0에서 m - 1까지 역순으로 i의 경우 다음을 수행합니다.
- i ~ m - 1 범위의 j에 대해 수행
  - k :=i + m - j - 1
  - dp[i, j] =(nums[i] * multipliers[k] + dp[i+1, j]) 및 (nums[j-m+n] * multipliers[k] + dp[i, j]의 최대값 -1])
dp[0]
의 마지막 요소를 반환합니다.

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(nums, multipliers):
   n, m = len(nums), len(multipliers)
   dp = [[0]*m for _ in range(m+1)]

   for i in reversed(range(m)):
      for j in range(i, m):
         k = i + m - j - 1
         dp[i][j] = max(nums[i] * multipliers[k] + dp[i+1][j], nums[j-m+n] * multipliers[k] + dp[i][j-1])

   return dp[0][-1]

nums = [5,10,15]
multipliers = [5,3,2]
print(solve(nums, multipliers))

입력

[5,10,15], [5,3,2]