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:=num_s的大小
如果n＜3，则：
- 定义一个大小为(n + 1)x(n + 1)的二维数组
初始化len := 3，当len＜= n时，更新（增加len）-
- 初始化i := 1，当i + len – 1＜= n时，更新（i增加1）-
  - r:=i+len -1
  - ans:=0
  - 初始化k: =i +1，当 k ＜r -1时，更新（增加k）-
  - curr：=dp[i，k]+ dp[k，r]+ nums[k-1]
  - 如果curr＞ans，则：
  - ans：=ans + nums[i-1]+ nums[r-1]
  - dp[i，r] ：=ans
返回dp [1, n]

让我们看下面的实现以更好地理解

更多Python相关文章，请阅读：Python 教程

示例

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