ปูพื้นฐาน

เร่งดีพีบนช่วงแบบคะนูธ: จุดตัดที่ดีที่สุดเดินไปทางเดียว จึงไม่ต้องส่องซ้ำ

ดีพีบนช่วงรูปที่พบบ่อยที่สุดยุบจาก O(n³) เหลือ O(n²) ได้ด้วยการเปลี่ยนขอบเขตของลูปในสุดสามบรรทัด บทนี้ปูสะพานสองอันที่ตำราข้าม คือทำไมต้องเป็นเพื่อนบ้านสองช่องนั้น และทำไมหน้าต่างที่แคบลงนิดเดียวถึงยุบได้ทั้งอันดับ พร้อมเกมเลือกลำดับตัดไม้ ตัวอย่างค้านที่ทำให้ตอบผิดแบบเงียบ ๆ และโจทย์ฝึกสามข้อจากคลังอ้างอิงของต้นทาง

ปัญหาที่บทนี้แก้

มีไม้ท่อนหนึ่ง ยาว 10 หน่วย บนไม้มีรอยกาไว้แล้วว่าต้องตัดตรงไหนบ้าง ตัดหนึ่งครั้งเสียเงินเท่ากับความยาวของชิ้นที่กำลังถูกตัด ไม่ใช่ความยาวของชิ้นที่ได้ออกมา คำถามคือ ตัดตามลำดับไหนถึงจะจ่ายน้อยที่สุด

จุดที่ทำให้โจทย์นี้ไม่ใช่โจทย์เด็ก ๆ คือ ลำดับมีผล ถ้าตัดไม้ท่อนยาวก่อน รอยที่เหลือจะอยู่ในชิ้นที่สั้นลงแล้ว จึงถูกลง กลับกัน ถ้าเก็บรอยกลางไว้ตัดทีหลัง รอยนั้นจะยังอยู่ในชิ้นยาว ๆ อยู่

เขียนสูตรได้ไม่ยาก มองไม้เป็น ช่องว่างระหว่างรอยกาที่ติดกัน ซึ่งไม้ต้นนี้มี 5 ช่อง ช่องหนึ่งคือของหนึ่งชิ้นที่ห้ามตัดอีกแล้ว การตัดหนึ่งครั้งจึงเป็นการ ผ่าช่วงของช่องออกเป็นสองช่วง โดยจ่ายเท่าความยาวรวมของช่วงที่กำลังผ่า

ตรงนี้ C(i, j) คือค่าใช้จ่ายที่ต้องจ่ายเมื่อผ่าช่วง [i..j] หนึ่งครั้ง ซึ่งในโจทย์ตัดไม้คือความยาวรวมของช่วงนั้น ส่วน k คือรอยที่เลือกผ่า

สูตรที่เขียนได้ กับตัวเลขที่ทำให้ตกรอบ

สูตรข้างบนมีช่องให้เติม n² ช่อง แต่ละช่องไล่ k ได้ถึง n จุด รวมเป็น O(n³) ซึ่งไหวถ้า n อยู่ระดับไม่กี่ร้อย พอโจทย์ให้ n เป็นหลักพัน มันก็ตกเวลาไปเฉย ๆ

ท่านี้เป็นญาติสนิทของบทแบ่งครึ่งเร่งดีพี ทั้งคู่ยืนอยู่บนความคิดเดียวกัน คือจุดตัดที่ดีที่สุดไม่ได้กระโดดไปมา ต่างกันที่รูปของโจทย์ ท่าแบ่งครึ่งใช้กับดีพีที่มี ชั้น (แบ่งของเป็น k กอง) ส่วนท่านี้ใช้กับ ดีพีบนช่วง ที่ช่วงหนึ่งแตกเป็นสองช่วงย่อย ถ้ายังไม่ได้อ่านสองบทนั้น อ่านบทนี้ก่อนก็ได้ แต่จะได้ประโยชน์มากขึ้นถ้าอ่านบทดีพีบนช่วงมาก่อน

ลองเอง · เลือกลำดับตัดไม้

ก่อนไปดูท่าเร่งความเร็ว ลองตัดเองก่อน กติกาคือคลิกที่รอยกาเพื่อตัดตรงนั้น ค่าที่ต้องจ่ายคือความยาวของชิ้นที่รอยนั้นอยู่ในขณะที่คลิก ตัดให้ครบทุกรอย แล้วดูว่ารวมแล้วได้เท่าไร

ชุดที่สามมีรอยกาสามรอยกระจุกอยู่ทางซ้าย ถ้าไล่ตัดเรียงจากรอยซ้ายสุดไปขวาสุด จะได้ 118 ขณะที่คำตอบจริงคือ 70 เพราะทุกครั้งที่ตัดรอยทางซ้าย ชิ้นที่ถืออยู่ยังยาวเกือบเต็มไม้

พอมีคำตอบในใจแล้ว มาดูกันว่าถ้าไม้ต้นนั้นมีรอยกาสามพันรอย เครื่องจะตัดงานทิ้งได้ยังไง

ของชิ้นเดียวที่เปลี่ยนทุกอย่าง คือจุดตัดที่ดีที่สุด

ตั้งชื่อให้มันก่อน เรียกว่า opt(i, j)

ชื่อ opt ย่อมาจาก optimal อ่านว่า "ออปทิมัล" แปลว่า "ดีที่สุด" มันไม่ใช่คำตอบของช่วงนั้น มันคือตำแหน่งที่ทำให้ได้คำตอบนั้น ต่างกันเหมือนคะแนนสอบกับเลขที่นั่งของคนที่ได้คะแนนนั้น

ทีนี้ลองพิมพ์ opt ของทุกช่องออกมาดู นี่คือของจริงจากไม้ยาว 10 ข้างบน แถวคือขอบซ้ายของช่วง คอลัมน์คือขอบขวา

เขียนสองข้อสังเกตนั้นเป็นบรรทัดเดียวได้แบบนี้

ประโยคนี้คือจุดที่ผมอ่านตำราแล้วสะดุด เพราะมันบอกแค่ว่าอสมการเป็นจริง แต่ไม่ได้บอกว่า ทำไมสองช่องนั้น ลองอ่านมันใหม่โดยมองที่ตารางแทนที่จะมองที่ตัวอักษร

• opt(i, j-1) คือช่องซ้ายมือของช่องที่กำลังจะเติม มันคือช่วงเดียวกันแต่ตัดหางขวาออกไปหนึ่งช่อง
• opt(i+1, j) คือช่องข้างล่าง มันคือช่วงเดียวกันแต่ตัดหัวซ้ายออกไปหนึ่งช่อง
• ทั้งสองช่องนั้นสั้นกว่าช่องที่กำลังเติมอยู่หนึ่งช่อง จึงถูกเติมไปแล้วแน่นอน ถ้าเราเติมตารางโดยไล่ตามความยาวช่วงจากสั้นไปยาว

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

ทำไมแคบลงนิดเดียวแล้วถึงยุบได้ทั้งอันดับ

ตรงนี้เป็นสะพานที่สองที่ตำรามักข้าม เพราะดูจากภาพข้างบน มันแคบลงแค่ไม่กี่ช่อง แล้วจะยุบจาก O(n³) เป็น O(n²) ได้ยังไง

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

พอขอบทั้งสองข้างเดินทางเดียว ผลรวมความยาวของแถบทั้งเส้นก็มีเพดานง่าย ๆ คือ ระยะที่ขอบขวาเดินได้ทั้งหมด บวกจำนวนแถบ เพราะแถบหนึ่งกินอย่างน้อยหนึ่งช่องเสมอ ในภาพข้างบนคือ 5 บวก 5 เท่ากับ 10 ซึ่งมากกว่างานจริง 9 ครั้งอยู่ ทั้งเส้นทแยงจึงเป็นงาน O(n) ไม่ใช่ O(n²) และมีเส้นทแยงทั้งหมด n เส้น รวมเป็น O(n²)

เดินให้ดูทีละขั้น

นี่คือการเติมตารางจริงของไม้ยาว 10 ต้นเดิม เดินไล่ตามความยาวช่วงจากสั้นไปยาว ช่องเขียวคือช่องที่กำลังเติม ช่องเหลืองคือเพื่อนบ้านสองช่องที่บอกขอบมาให้

เดินครบทั้งตารางแล้ว ท่านี้ส่องจุดตัดรวม 17 ครั้ง ส่วนการไล่ทุกจุดต้องส่อง 20 ครั้ง ประหยัดไป 3 ครั้ง ซึ่งดูน้อยเพราะไม้ต้นนี้เล็ก ความต่างจริงอยู่ในตารางวัดเวลาข้างบน

เงื่อนไขที่ต้องจริงก่อน ถึงจะใช้ท่านี้ได้

ข้ออ้างเรื่อง opt ไม่ถูกต้องฟรี ๆ มันต้องการเงื่อนไขสองข้อกับฟังก์ชันค่าใช้จ่าย C ทั้งสองข้อพูดถึงช่วงสี่ตำแหน่งที่เรียงกันคือ a ถึง b ถึง c ถึง d

ข้อแรกคือ ค่าใช้จ่ายต้องโตตามช่วง ช่วงที่อยู่ข้างในต้องไม่แพงกว่าช่วงที่ครอบมันอยู่

ข้อสองชื่อ อสมการสี่เหลี่ยม (quadrangle inequality อ่านว่า "ควอดแรงเกิล อินอิควอลิตี" แปลตรงตัวว่า "อสมการสี่เหลี่ยม" ตั้งชื่อตามการที่มันพูดถึงสี่จุดพร้อมกัน)

อสมการข้อสองนี้อ่านยากถ้าดูแค่ตัวอักษร ลองอ่านเป็นภาษาคน ฝั่งซ้ายคือช่วงคู่หนึ่งที่ เหลื่อมกัน คือ [a..c] กับ [b..d] ส่วนฝั่งขวาคือช่วงคู่หนึ่งที่ ซ้อนกัน คือ [a..d] ที่ครอบ [b..c] ไว้ทั้งอัน ทั้งสองคู่กินตำแหน่งรวมกันเท่ากันเป๊ะ อสมการจึงบอกว่า แบบซ้อนกันแพงกว่าหรือเท่ากับแบบเหลื่อมกันเสมอ พูดอีกทางคือค่าใช้จ่ายลงโทษการมีช่วงยาว ๆ มากกว่าลงโทษการมีช่วงกลาง ๆ สองช่วง

ถ้าฝืนใช้กับค่าใช้จ่ายที่ไม่เข้าเงื่อนไข จะพังยังไง

ตรงนี้สำคัญกว่าที่คิด เพราะเวลาข้ออ้างไม่จริง โปรแกรมไม่พังและไม่ฟ้องอะไรเลย มันแค่ตอบค่าที่มากกว่าคำตอบจริงอย่างเงียบ ๆ เฉพาะบางอินพุต

ตัวค้านที่เล็กที่สุดที่ผมหาเจอมีแค่ 4 ช่อง และค่าใช้จ่ายเป็นศูนย์ทุกช่องยกเว้นสองช่อง คือ C(1,2) = 1 กับ C(2,4) = 1 ที่เหลือเป็นศูนย์หมด ไล่จุดตัดทุกจุดได้คำตอบ 0 แต่ใส่หน้าต่างของ Knuth แล้วได้ 1

ค่าใช้จ่ายชุดนี้พังทั้งสองเงื่อนไข อสมการสี่เหลี่ยมพังที่ a=1 b=2 c=2 d=3 และเงื่อนไขโตตามช่วงพังที่ a=1 b=1 c=2 d=3 ส่วนค่าใช้จ่ายแบบผลรวมของช่วง ผมไล่ตรวจทุกสี่จุดในไม้ตัวอย่างแล้ว ผ่านทั้งสองข้อ

แม่แบบที่ลอกไปใช้ได้ทุกข้อ

เทียบกับดีพีบนช่วงธรรมดา โค้ดนี้ต่างกันแค่สามบรรทัด คือตาราง opt กับ lo และ hi

// แม่แบบ Knuth optimization สำหรับรูป dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C(i, j)
// เปลี่ยนแค่ฟังก์ชัน C กับการอ่านอินพุต ที่เหลือลอกทั้งก้อน
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
ll C(int i, int j);              // ค่าใช้จ่ายของช่วง i..j

const ll INF = (ll)4e18;

ll solve() {
    vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));
    vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));

    // ช่วงยาวหนึ่งช่องไม่มีอะไรให้ตัด และเป็นที่ที่หน้าต่างเริ่มนับ
    for (int i = 1; i <= n; i++) { dp[i][i] = 0; opt[i][i] = i; }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            // ขอบซ้ายมาจากช่องซ้ายมือ ขอบขวามาจากช่องข้างล่าง ทั้งคู่เติมไปแล้ว
            int lo = max(opt[i][j - 1], i);
            int hi = min(opt[i + 1][j], j - 1);
            for (int k = lo; k <= hi; k++) {
                ll cand = dp[i][k] + dp[k + 1][j] + C(i, j);
                if (cand < dp[i][j]) { dp[i][j] = cand; opt[i][j] = k; }
            }
        }
    }
    return n ? dp[1][n] : 0;
}

โจทย์ฝึก · ไล่จากง่ายไปยาก

สามข้อนี้หยิบมาจากรายการอ้างอิงท้ายหน้า Knuth optimization ของ cp-algorithms เรียงให้ข้อแรกใช้ท่านี้ก็ได้ไม่ใช้ก็ได้ ข้อสองบังคับให้ใช้ และข้อสามเปลี่ยนหน้าตาของค่าใช้จ่าย

ฝึกข้อ 1 · ตัดไม้ (UVA 10003 Cutting Sticks)

ช่างไม้รับไม้มาท่อนหนึ่ง ลูกค้าทำเครื่องหมายไว้ว่าต้องตัดตรงไหนบ้าง ร้านคิดเงินตามความยาวของชิ้นที่กำลังตัด ช่างจึงเลือกลำดับเองได้ ให้หาว่าจ่ายน้อยที่สุดเท่าไร

เฉลยฝึกข้อ 1

โค้ดฝึกข้อ 1

// Cutting Sticks: ไม้ยาว L มีรอยกา n รอย ตัดหนึ่งครั้งเสียเท่าความยาวชิ้นที่กำลังตัด
// อินพุต: L แล้ว n แล้วตำแหน่งรอยกา n ตัว จบไฟล์เมื่อ L = 0
// เอาต์พุต: The minimum cutting is <ค่าน้อยสุด>.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = (ll)4e18;

int main() {
    ll L;
    while (scanf("%lld", &L) == 1 && L != 0) {
        int c; scanf("%d", &c);
        vector<ll> mark(c + 2);
        mark[0] = 0;
        for (int t = 1; t <= c; t++) scanf("%lld", &mark[t]);
        mark[c + 1] = L;

        // ช่องว่างระหว่างรอยกาที่ติดกัน หนึ่งช่องคือของหนึ่งชิ้นที่ห้ามตัดอีก
        int n = c + 1;
        vector<ll> pre(n + 1, 0);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (mark[i] - mark[i - 1]);
        auto C = [&](int i, int j) { return pre[j] - pre[i - 1]; };

        vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));
        vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));
        for (int i = 1; i <= n; i++) { dp[i][i] = 0; opt[i][i] = i; }

        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = INF;
                int lo = max(opt[i][j - 1], i);
                int hi = min(opt[i + 1][j], j - 1);
                for (int k = lo; k <= hi; k++) {
                    ll cand = dp[i][k] + dp[k + 1][j] + C(i, j);
                    if (cand < dp[i][j]) { dp[i][j] = cand; opt[i][j] = k; }
                }
            }

        printf("The minimum cutting is %lld.\n", dp[1][n]);
    }
    return 0;
}

ฝึกข้อ 2 · หักสตริง (SPOJ BRKSTRNG Breaking String)

เรื่องเดียวกันเป๊ะ เปลี่ยนจากไม้เป็นสายอักขระ ต้องหักสายที่ตำแหน่งที่กำหนดให้ครบทุกตำแหน่ง หักหนึ่งครั้งเสียเท่าความยาวของสายที่กำลังหัก จุดเดียวที่ต่างคือขอบเขต

เฉลยฝึกข้อ 2

โค้ดฝึกข้อ 2

// Breaking String: เรื่องเดียวกับตัดไม้ แต่ n ถึงหนึ่งพันและมีหลายชุดทดสอบ
// จุดเดียวที่ต่างจากข้อแรกคือขอบเขต ซึ่งเป็นตัวบังคับว่าต้องใส่หน้าต่างของ Knuth
// อินพุต: L m แล้วตำแหน่งที่ต้องหัก m ตัว  เอาต์พุต: ค่าน้อยสุดของแต่ละชุด
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = (ll)4e18;

int main() {
    ll L; int m;
    while (scanf("%lld %d", &L, &m) == 2) {
        vector<ll> mark(m + 2);
        mark[0] = 0;
        for (int t = 1; t <= m; t++) scanf("%lld", &mark[t]);
        mark[m + 1] = L;

        int n = m + 1;
        vector<ll> pre(n + 1, 0);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (mark[i] - mark[i - 1]);
        auto C = [&](int i, int j) { return pre[j] - pre[i - 1]; };

        vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));
        vector<vector<int>> opt(n + 2, vector<int>(n + 2, 0));
        for (int i = 1; i <= n; i++) { dp[i][i] = 0; opt[i][i] = i; }

        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = INF;
                int lo = max(opt[i][j - 1], i);
                int hi = min(opt[i + 1][j], j - 1);
                for (int k = lo; k <= hi; k++) {
                    ll cand = dp[i][k] + dp[k + 1][j] + C(i, j);
                    if (cand < dp[i][j]) { dp[i][j] = cand; opt[i][j] = k; }
                }
            }

        printf("%lld\n", n ? dp[1][n] : 0);
    }
    return 0;
}

ฝึกข้อ 3 · ต้นไม้ค้นหาที่ดีที่สุด (UVA 10304 Optimal Binary Search Tree)

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

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

เฉลยฝึกข้อ 3

โค้ดฝึกข้อ 3

// Optimal Binary Search Tree: ของ n อย่างเรียงตามชื่ออยู่แล้ว แต่ละอย่างมีความถี่ f[i]
// จัดเป็นต้นไม้ค้นหา ให้ผลรวมของ ความถี่ คูณ ชั้นที่มันอยู่ น้อยที่สุด (รากคือชั้นที่ 1)
// รูปนี้ต่างจากแม่แบบนิดเดียว คือ k เป็น "ราก" ซึ่งถูกดึงออกจากทั้งสองข้าง
// จึงเป็น g[i][k-1] กับ g[k+1][j] และ k เดินได้ถึง j ไม่ใช่ j-1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = (ll)4e18;

int main() {
    int n;
    while (scanf("%d", &n) == 1 && n > 0) {
        vector<ll> f(n + 1, 0), pre(n + 1, 0);
        for (int i = 1; i <= n; i++) { scanf("%lld", &f[i]); pre[i] = pre[i - 1] + f[i]; }
        auto S = [&](int i, int j) { return i > j ? 0LL : pre[j] - pre[i - 1]; };

        vector<vector<ll>> g(n + 3, vector<ll>(n + 3, 0));
        vector<vector<int>> opt(n + 3, vector<int>(n + 3, 0));
        for (int i = 1; i <= n; i++) { g[i][i] = f[i]; opt[i][i] = i; }

        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                g[i][j] = INF;
                int lo = max(opt[i][j - 1], i);
                int hi = min(opt[i + 1][j], j);      // ถึง j เพราะรากเป็นตัวขวาสุดได้
                for (int k = lo; k <= hi; k++) {
                    ll cand = (k > i ? g[i][k - 1] : 0) + (k < j ? g[k + 1][j] : 0) + S(i, j);
                    if (cand < g[i][j]) { g[i][j] = cand; opt[i][j] = k; }
                }
            }

        printf("%lld\n", n ? g[1][n] : 0);
    }
    return 0;
}

ตัวตรวจที่ควรเขียนคู่กันทุกครั้ง

นี่คือกรณีที่ตัวตรวจสำคัญที่สุดเท่าที่มีในคลังนี้ เพราะข้ออ้างของ Knuth เป็นข้ออ้างเชิงทฤษฎีที่ ถ้าไม่จริง โค้ดจะไม่ฟ้องอะไรเลย ไม่มี segmentation fault ไม่มีลูปไม่รู้จบ มีแต่ตัวเลขที่ใหญ่กว่าคำตอบจริงนิดหน่อยในบางอินพุต

// ตัวตรวจอิสระ: ไล่จุดตัดทุกจุดจริง ไม่ใช้ข้ออ้างเรื่อง opt เลยแม้แต่นิดเดียว
// นี่คือ O(n^3) ซึ่งเป็นสิ่งที่ Knuth พยายามหลบ จึงเป็นการตรวจที่อิสระจริง
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (ll)4e18;

int n; vector<ll> pre;
ll C(int i, int j) { return pre[j] - pre[i - 1]; }

ll cubic() {
    vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, 0));
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            dp[i][j] = INF;
            for (int k = i; k < j; k++)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + C(i, j));
        }
    return n ? dp[1][n] : 0;
}

// ตัวตรวจชั้นที่สอง: ไล่ "ลำดับการตัด" ทุกแบบ ไม่ใช้ดีพีเลย
// ชั้นนี้สำคัญกว่า เพราะมันไม่ได้เชื่อแม้แต่ว่าโจทย์นี้เป็นดีพีบนช่วง
map<vector<pair<int,int>>, ll> memo;
ll byOrder(vector<pair<int,int>> st) {
    vector<pair<int,int>> live;
    for (auto &p : st) if (p.second > p.first) live.push_back(p);
    if (live.empty()) return 0;
    sort(live.begin(), live.end());
    auto it = memo.find(live);
    if (it != memo.end()) return it->second;
    ll best = INF;
    for (size_t idx = 0; idx < live.size(); idx++) {
        auto [l, r] = live[idx];
        ll price = C(l, r);
        for (int c = l; c < r; c++) {
            vector<pair<int,int>> ns;
            for (size_t t = 0; t < live.size(); t++) if (t != idx) ns.push_back(live[t]);
            ns.push_back({l, c}); ns.push_back({c + 1, r});
            best = min(best, price + byOrder(ns));
        }
    }
    memo[live] = best;
    return best;
}

int main() {
    mt19937 rng(12345);
    for (int t = 0; t < 4000; t++) {
        n = 1 + rng() % 9;
        pre.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + (1 + rng() % 12);
        ll a = cubic();
        if (n <= 6) { memo.clear(); if (byOrder({{1, n}}) != a) { puts("ORDER MISMATCH"); return 1; } }
        // เอา a ไปเทียบกับผลของโค้ด Knuth ที่กำลังจะส่ง
    }
    puts("OK");
    return 0;
}

สรุปบรรทัดเดียว

ถ้าดีพีบนช่วงของคุณมีรูป dp[i][j] = min(dp[i][k] + dp[k+1][j]) + C(i, j) และ C เป็นผลรวมของค่าที่ไม่ติดลบในช่วง ให้เก็บตาราง opt เพิ่มอีกใบ แล้วเปลี่ยนลูปในสุดจาก i ถึง j-1 เป็น opt[i][j-1] ถึง opt[i+1][j] เท่านี้ O(n³) ก็ยุบเป็น O(n²) โดยคำตอบเท่าเดิม

ท่านี้ไม่ได้ทำให้แต่ละช่องเร็วขึ้น มันทำให้ขอบของหน้าต่างเดินไปทางเดียวตลอดทั้งเส้นทแยง แล้วงานทั้งเส้นก็ถูกนับรวมได้ทีเดียว

ที่มาและอ่านต่อ

1. cp-algorithms, "Knuth's Optimization" ต้นทางของบทนี้ ทั้งเงื่อนไขสองข้อ อสมการเรื่อง opt และรายการโจทย์ฝึกท้ายหน้า cp-algorithms.com
2. F. F. Yao, "Efficient Dynamic Programming Using Quadrangle Inequalities" (1980) งานที่พิสูจน์ว่าอสมการสี่เหลี่ยมทำให้ opt ขยับทางเดียว ซึ่งเป็นฐานของทั้งบท
3. D. E. Knuth, "Optimum binary search trees" (1971) ที่มาของชื่อท่า และของโจทย์ฝึกข้อที่ 3
4. UVA 10003 Cutting Sticks, SPOJ BRKSTRNG Breaking String, UVA 10304 Optimal Binary Search Tree
5. ในคลังนี้: DP บนช่วง คือบทที่ควรอ่านก่อน และ แบ่งครึ่งเร่งดีพี คือท่าพี่น้องที่ใช้กับดีพีแบบมีชั้น