数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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) 的二维数组
- 用于初始化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 > ans，则
- ans := ans + nums[i - 1] + nums[r - 1]
- dp[i, r] := 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
更新于：2020年11月20日
127 次浏览
广告