Pythonで数値を削除して最大の加法スコアを見つけるプログラム

numsという番号のリストがあるとします。数値を選択し、それを削除して、その数値とそれに隣接する2つの数値の合計でスコアを増やすことができる操作を考えてみましょう。リストの最初または最後の番号を選択しない限り、この操作を何度でも実行できる場合。可能な最大スコアを見つける必要があります。

したがって、入力が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配列を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
• return 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