Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬에서 숫자를 삭제하여 최대 가산 점수를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정합니다. 숫자를 선택한 다음 제거하고 숫자와 인접한 두 숫자의 합으로 점수를 높이는 작업을 고려해 보겠습니다. 목록에서 첫 번째 또는 마지막 숫자를 선택하지 않는 한 이 작업을 원하는 만큼 수행할 수 있습니다. 가능한 최대 점수를 찾아야 합니다.

따라서 입력이 nums =[2, 3, 4, 5, 6]과 같으면 5를 선택할 수 있으므로 출력은 39가 되고 합계는 (4 + 5 + 6) =15가 되고 배열은 [2, 3, 4, 6]이고 4를 선택하면 합계는 (3 + 4 + 6) =13이고 배열은 [2, 3, 6]이 되고 3을 선택하면 합계는 (2 + 3)이 됩니다. + 6) =11이므로 총합은 15 + 13 + 11 =39입니다.

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

  • n :=숫자 크기
  • n <3이면:
    • (n + 1) x (n + 1) 크기의 2D 배열 하나 정의
  • len 초기화의 경우:=3, len <=n일 때 업데이트(len 1씩 증가), 수행 -
    • i를 초기화하기 위해:=1, i + len - 1 <=n일 때 업데이트(i를 1만큼 증가), −
      • r :=i + len - 1
      • ans :=0
      • 초기화 k의 경우:=i + 1, k <=r - 1일 때 업데이트(k를 1만큼 증가), 수행 -
        • curr :=dp[i, k] + dp[k, r] + nums[k - 1]
        • curr> an이면:
      • ans :=ans + nums[i - 1] + nums[r - 1]
      • dp[i, r] :=ans
  • dp[1, n]을 반환

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

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& nums) {
      int n = nums.size();
      if (n < 3) return 0;
         vector<vector<int>> dp(n + 1, vector<int>(n + 1));
         for (int len = 3;
            len <= n; ++len) {
               for (int i = 1; i + len - 1 <= n; ++i) {
                  int r = i + len - 1;
                  int ans = 0;
               for (int k = i + 1; k <= r - 1; ++k) {
                  int curr = dp[i][k] + dp[k][r] + nums[k - 1];
                  if (curr > ans)
                     ans = curr;
               }
               ans += nums[i - 1] + nums[r - 1]; dp[i][r] = ans;
         }
      }
      return dp[1][n];
   }
};
int solve(vector<int>& nums) {
   return (new Solution())->solve(nums);
}
main(){
   vector<int> v = {2, 3, 4, 5, 6};
   cout << solve(v);
}

입력

[2, 3, 4, 5, 6]

출력

39