程序通过删除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