โปรแกรมค้นหาคะแนนการเติมสูงสุดโดยการลบตัวเลขใน 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 แล้ว:
  • กำหนดขนาดอาร์เรย์ 2 มิติหนึ่งชุด (n + 1) x (n + 1)
• สำหรับการเริ่มต้น len :=3 เมื่อ len <=n อัปเดต (เพิ่ม len โดย 1) ทำ −
  • สำหรับการเริ่มต้น i :=1 เมื่อ i + len - 1 <=n อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
    • r :=i + len - 1
    • ตอบ :=0
    • สำหรับการเริ่มต้น k :=i + 1 เมื่อ k <=r - 1 อัปเดต (เพิ่ม k ขึ้น 1) ทำ −
      • curr :=dp[i, k] + dp[k, r] + nums[k - 1]
      • ถ้า curr> ตอบ แล้ว:
    • 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);
}

อินพุต

[2, 3, 4, 5, 6]

ผลลัพธ์

39