โปรแกรมค้นหาจำนวนการดำเนินการที่จำเป็นในการลบรายการย่อยพาลินโดรมใน C++

สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums ตอนนี้ให้เราพิจารณาการดำเนินการที่เราลบรายการย่อยบางส่วนซึ่งเป็นพาลินโดรม เราต้องหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นเพื่อให้รายการว่างเปล่า

ดังนั้น หากอินพุตเป็น nums =[6, 2, 4, 4, 2, 10, 6] ผลลัพธ์จะเป็น 2 เนื่องจากเราสามารถลบรายการย่อย [2, 4, 4, 2] ออกก่อน จากนั้น รายการก็เหมือน [6, 10, 6] นี่เป็นพาลินโดรมด้วย ดังนั้นให้ลบออกเพื่อให้รายการว่าง

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดขนาดอาร์เรย์ dp:105 x 105

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ i, j, อาร์เรย์ v

• ret :=inf

• ถ้าฉัน> j แล้ว −

  • คืนค่า 0

• ถ้าฉันเหมือนกับ j แล้ว −

  • กลับ 1

• ถ้า j - i เท่ากับ 1 แล้ว −

  • return (ถ้า v[i] เหมือนกับ v[j] แล้ว 1 มิฉะนั้น 2)

• ถ้า i + 1 <=j และ v[i] เหมือนกับ v[i + 1] แล้ว −

  • ret :=1 + dfs(i + 2, j, v)

• ถ้า dp[i, j] ไม่เท่ากับ -1 แล้ว −

  • กลับ dp[i, j]

• ret :=ขั้นต่ำของ (ret, 1 + (ขั้นต่ำของ (dfs(i + 1, j, v) และ dfs(i, j - 1, v)))

• ถ้า v[i] เหมือนกับ v[j] แล้ว −

  • ret :=ขั้นต่ำของ ret และ dfs(i + 1, j - 1, v)

• สำหรับการเริ่มต้น k :=i + 2 เมื่อ k

  • ถ้า v[i] เหมือนกับ v[k] แล้ว &minnus;

    • ret :=ขั้นต่ำของ ret และ dfs((i + 1, k - 1, v) + dfs(k + 1, j, v))

• กลับ dp[i, j] =ret

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• เติม dp ด้วย -1

• n :=ขนาดของ nums

• ส่งคืน dfs(0, n - 1, nums)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
   int ret= INT_MAX;
   if(i > j)
      return 0;
   if(i == j)
      return 1;
   if(j - i == 1){
      return v[i] == v[j] ? 1 : 2;
   }
   if(i + 1 <= j && v[i] == v[i + 1]){
      ret = 1 + dfs(i + 2, j, v);
   }
   if(dp[i][j] != -1) return dp[i][j];
      ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
   if(v[i] == v[j]){
      ret = min(ret, dfs(i + 1, j - 1, v));
   }
   for(int k = i + 2; k < j; k++){
      if(v[i] == v[k]){
         ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
      }
   }
   return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
   memset(dp , -1, sizeof dp);
   int n = nums.size();
   return dfs(0, n - 1, nums);
}
int main(){
   vector<int> v = {6, 2, 4, 4, 2, 10, 6};
   cout << solve(v);
}

อินพุต

{6, 2, 4, 4, 2, 10, 6}

ผลลัพธ์

2