程序通过删除Python中的数字来查找最高加分

假设我们有一个称为nums的数字列表。让我们考虑一个操作，在该操作中我们可以选择一个数字，然后将其删除，并通过该数字及其两个相邻数字的总和来增加分数。如果我们可以执行任意次数的此操作，只要不选择列表中的第一个或最后一个数字。我们必须找到可能的最高分。

因此，如果输入像nums = [2、3、4、5、6]，则输出将为39，因为我们可以选择5，所以总和为（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：= nums的大小

• 如果n <3，则：

• 定义一个大小为（n + 1）x（n + 1）的2D数组

• 对于初始化len：= 3，当len <= n时，更新（将len增加1），执行-

• r：= i + len-1

• 回答：= 0

• 对于初始化k：= i + 1，当k <= r-1，更新（k增加1），做-

• ans：= ans + nums [i-1] + nums [r-1]

• dp [i，r]：= ans

• curr：= dp [i，k] + dp [k，r] + nums [k-1]

• 如果curr> ans，则：

• 对于初始化i：= 1，当i + len-1 <= n时，更新（将i增加1），-

• 返回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