โปรแกรมค้นหาต้นทุนต่ำสุดของต้นไม้การแยกวิเคราะห์ใน C++

สมมติว่าเรามีรายการตัวเลขที่ไม่ซ้ำกันและเรียงลำดับแล้ว ซึ่งแสดงจุดแบ่ง (breakpoints) ในสตริง เราต้องการสร้างต้นไม้จากกฎเหล่านี้:

• มีโหนดที่มีค่า (a, b) โดยที่ a และ b เป็นจุดแบ่ง หมายความว่าโหนดครอบคลุมดัชนี [a, b] ในสตริง
• โหนดรากครอบคลุมทุกจุดแบ่ง (ทั้งสตริงทั้งหมด)
• ช่วงของลูกซ้ายและลูกขวาของโหนดจะเรียงลำดับ ติดกัน และครอบคลุมช่วงของโหนดแม่
• ดัชนีของ 'a' ในจุดแบ่งของโหนดใบจะอยู่ก่อนดัชนีของ 'b' หนึ่งตำแหน่ง

ต้นทุนของต้นไม้คำนวณจากผลรวมของ b - a สำหรับทุกโหนดในต้นไม้ เป้าหมายคือหาต้นทุนต่ำสุดที่เป็นไปได้ของต้นไม้ที่ถูกต้อง

ตัวอย่างเช่น หากอินพุตคือ breakpoints = [1, 4, 7, 12] ผลลัพธ์จะเป็น 28

ขั้นตอนการแก้ปัญหา

1. n := ขนาดของอาร์เรย์อินพุต breakpoints
2. ถ้า n <= 1 ให้คืนค่า 0
3. ถ้า n = 2 ให้คืนค่า breakpoints[1] - breakpoints[0]
4. สร้างอาร์เรย์ p[n-1] โดย p[i] = breakpoints[i+1] - breakpoints[i]
5. สร้างอาร์เรย์คำนำหน้าสะสม pre[n] โดย pre[i] = pre[i-1] + p[i-1]
6. สร้างอาร์เรย์ 2 มิติ dp[n][n] เริ่มต้นด้วยค่าความลانهائية และอาร์เรย์ op[n][n]
7. กำหนดค่าเริ่มต้น: dp[i][i] = p[i-1], op[i][i] = i สำหรับ i = 1 ถึง n-1
8. ใช้การ برنامهไดนามิกพร้อมการเพิ่มประสิทธิภาพ Knuth:
   • สำหรับความยาว len = 2 ถึง n-1
   • สำหรับ i = 1 ถึง n-len
   • j = i + len - 1
   • ค้นหา k ที่เหมาะสมในช่วง [max(i, op[i][j-1]), min(j-1, op[i+1][j])]
   • อัปเดต dp[i][j] และ op[i][j]
   • เพิ่มค่า pre[j] - pre[i-1] เข้าไปใน dp[i][j]
9. คืนค่า dp[1][n-1]

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

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& breakpoints) {
    int n = breakpoints.size();
    if (n <= 1) return 0;
    if (n == 2) return breakpoints[1] - breakpoints[0];
    
    vector<int> p(n - 1);
    for (int i = 0; i < n - 1; ++i) 
        p[i] = breakpoints[i + 1] - breakpoints[i];
    
    vector<int> pre(n);
    for (int i = 1; i < n; ++i) 
        pre[i] = pre[i - 1] + p[i - 1];
    
    vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
    vector<vector<int>> op(n, vector<int>(n));
    
    for (int i = 1; i < n; ++i) 
        dp[i][i] = p[i - 1], op[i][i] = i;
    
    for (int len = 2; len < n; ++len) {
        for (int i = 1; i + len - 1 < n; ++i) {
            int j = i + len - 1;
            int idx = i;
            for (int k = max(i, op[i][j - 1]); k <= min(j - 1, op[i + 1][j]); ++k) {
                int cost = dp[i][k] + dp[k + 1][j];
                if (cost < dp[i][j]) {
                    idx = k;
                    dp[i][j] = cost;
                }
            }
            op[i][j] = idx;
            dp[i][j] += pre[j] - pre[i - 1];
        }
    }
    return dp[1][n - 1];
}

int main() {
    vector<int> breakpoints = {1, 4, 7, 12};
    cout << solve(breakpoints) << endl;
    return 0;
}

อินพุต

{1, 4, 7, 12}

เอาต์พุต

28