ขั้นตอนต่ำสุดในการลบสตริงหลังจากการลบ substring แบบพาลินโดรมซ้ำๆ ใน C++

ข้อกำหนดโจทย์

กำหนดสตริงที่มีตัวอักษรเป็นตัวเลขเท่านั้น เราต้องลบตัวอักษรทั้งหมดของสตริงนี้ในจำนวนขั้นตอนน้อยที่สุด โดยในหนึ่งขั้นตอนเราสามารถลบ substring ที่เป็นพาลินโดรมได้ หลังจากลบ substring ส่วนที่เหลือจะถูกต่อกัน

ตัวอย่าง

ถ้าสตริงอินพุตคือ 3441213 แล้วต้องใช้ขั้นตอนต่ำสุด 2 ขั้นตอน

• ลบ 121 ออกจากสตริงก่อน สตริงที่เหลือคือ 3443
• ลบสตริงที่เหลือเพราะมันเป็นพาลินโดรม

อัลกอริทึม

เราสามารถใช้ Dynamic Programming เพื่อแก้ปัญหานี้

1. ให้ dp[i][j] แทนจำนวนขั้นตอนที่ใช้ในการลบ substring s[i, j]
2. แต่ละตัวอักษรจะถูกลบคนเดียวหรือเป็นส่วนหนึ่งของ substring ดังนั้นในกรณีแรกเราจะลบตัวอักษรเองและเรียก subproblem (i+1, j)
3. ในกรณีที่สอง เราจะวนลูปทุกครั้งที่ตัวอักษรปัจจุบันปรากฏทางขวา ถ้า K เป็นดัชนีของหนึ่งครั้ง ปัญหาจะลดลงเหลือสอง subproblems (i+1, K-1) และ (K+1, j)
4. เราสามารถเข้าถึง subproblem (i+1, K-1) ได้เพราะเราสามารถลบตัวอักษรเดียวกันและเรียกสำหรับ substring กลาง
5. เราต้องดูแลกรณีที่ตัวอักษรสองตัวแรกเหมือนกัน ในกรณีนั้นเราสามารถลดโดยตรงไปที่ subproblem (i+2, j)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
  int n = str.length();
  int dp[n + 1][n + 1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      dp[i][j] = 0;
    }
  }
  for (int len = 1; len <= n; len++) {
    for (int i = 0, j = len - 1; j < n; i++, j++) {
      if (len == 1)
        dp[i][j] = 1;
      else {
        dp[i][j] = 1 + dp[i + 1][j];
        if (str[i] == str[i + 1]) {
          dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
        }
        for (int K = i + 2; K <= j; K++){
          if (str[i] == str[K]) {
            dp[i][j] = min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
          }
        }
      }
    }
  }
  return dp[0][n - 1];
}
int main() {
  string str = "3441213";
  cout << "Minimum required steps: " << getMinRequiredSteps(str) << endl;
  return 0;
}

เมื่อคุณคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้

ผลลัพธ์

Minimum required steps: 2