用 Python 编写的通过删除数字来查找最大加法分数的程序

pythonserver side programmingprogramming

假设我们有一个名为 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 的大小
if 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
返回 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);
}