Chương trình tìm điểm cộng tối đa bằng cách xóa số trong Python

Giả sử chúng ta có một danh sách các số được gọi là nums. Chúng ta hãy xem xét một phép toán trong đó chúng ta có thể chọn một số, sau đó loại bỏ nó và tăng điểm của chúng ta bằng tổng của số đó và hai số liền kề của nó. Nếu chúng ta có thể thực hiện thao tác này bao nhiêu lần tùy thích miễn là chúng ta không chọn số đầu tiên hoặc số cuối cùng trong danh sách. Chúng tôi phải tìm điểm tối đa có thể.

Vì vậy, nếu đầu vào là nums =[2, 3, 4, 5, 6], thì đầu ra sẽ là 39, vì chúng ta có thể chọn 5, khi đó tổng sẽ là (4 + 5 + 6) =15, mảng sẽ là [2, 3, 4, 6], sau đó chọn 4, vì vậy tổng là (3 + 4 + 6) =13 và mảng sẽ là [2, 3, 6], chọn 3, tổng sẽ là (2 + 3 + 6) =11, Vậy tổng cộng là 15 + 13 + 11 =39

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• nếu n <3, thì:
  • Xác định một mảng 2D có kích thước (n + 1) x (n + 1)
• để khởi tạo len:=3, khi len <=n, cập nhật (tăng len lên 1), do -
  • để khởi tạo i:=1, khi i + len - 1 <=n, cập nhật (tăng i lên 1), thực hiện -
    • r:=i + len - 1
    • ans:=0
    • để khởi tạo k:=i + 1, khi k <=r - 1, cập nhật (tăng k lên 1), thực hiện -
      • curr:=dp [i, k] + dp [k, r] + nums [k - 1]
      • if curr> ans, then:
    • ans:=ans + nums [i - 1] + nums [r - 1]
    • dp [i, r]:=ans
• trả về dp [1, n]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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);
}

Đầu vào

[2, 3, 4, 5, 6]

Đầu ra

39