24.4 บ้านติดกันและช่วงย่อยมากสุด

โจทย์สองข้อในหน้านี้ให้ข้อมูลเรียงเป็นแถว แล้วให้เลือกบางตัวให้ได้ผลรวมมากที่สุดภายใต้กติกา ข้อแรกห้ามเลือกสองตัวที่ติดกัน ข้อสองต้องเลือกเป็นช่วงติดกัน การลองทุกแบบเป็นงานของบทที่ 21 ซึ่งมีถึง 2^N แบบ แต่ DP หนึ่งมิติทำได้ใน O(N) ทั้งคู่ ข้อสองจะเห็นเรื่องใหม่ที่สำคัญ คือบางครั้งต้องนิยามสถานะให้แคบกว่าคำถาม แล้วคำตอบไม่ได้อยู่ช่องสุดท้าย

บ้านติดกันห้ามขโมยสองหลัง

โจทย์นี้มีชื่อในวงการว่า house robber บ้าน N หลังเรียงริมถนน หลังที่ i มีเงิน a_i บาท ขโมยในนิทานเข้าบ้านกี่หลังก็ได้ แต่ถ้าเข้าบ้านสองหลังที่ติดกัน สัญญาณกันขโมยจะดัง ถามว่าได้เงินมากที่สุดเท่าไร

ลองกับเงิน 20 50 30 10 60 40 30 เลือกหลังที่เงินมากที่สุดก่อนแบบ greedy ได้หลังที่ 5 (60) แล้วหลังที่ 2 (50) แล้วหลังที่ 7 (30) รวม 140 ซึ่งบังเอิญถูก แต่ถ้าเงินเป็น 50 60 50 greedy หยิบ 60 แล้วหยิบอะไรต่อไม่ได้ ทั้งที่ 50 + 50 = 100 ดีกว่า

1. สถานะ best[i] คือเงินมากที่สุดที่ได้จากบ้านหลังที่ 1 ถึง i เท่านั้น
2. ความสัมพันธ์ ดูการตัดสินใจกับหลังสุดท้ายคือหลังที่ i ถ้าไม่เข้า ก็เหมือนมีแค่บ้าน 1 ถึง i - 1 ได้ best[i - 1] ถ้าเข้า ห้ามเข้าหลัง i - 1 จึงได้ best[i - 2] + a[i] เลือกค่าที่มากกว่า
3. กรณีฐาน best[0] = 0 ไม่มีบ้านก็ไม่ได้เงิน และ best[1] = a[1]
4. เติม i จาก 2 ถึง N ตอบ best[N]

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

int main()
{
    int n;
    cin >> n;
    vector<long long> money(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> money[i];
    }
    vector<long long> best(n + 1);
    best[0] = 0; // (1)!
    best[1] = money[1];
    for (int i = 2; i <= n; i++) {
        best[i] = max(best[i - 1], best[i - 2] + money[i]); // (2)!
    }
    for (int i = 0; i <= n; i++) {
        cout << best[i] << (i < n ? ' ' : '\n');
    }
    return 0;
}

1. ใช้ช่อง 1 ถึง n เก็บบ้าน ให้เลขช่องตรงกับเลขบ้าน แล้วช่อง 0 ใช้เป็นกรณีฐาน "ไม่มีบ้าน" ได้พอดี ช่วยให้ best[i - 2] ตอน i = 2 อ่านช่อง 0 ได้โดยไม่ต้องมีกรณีพิเศษ
2. สองทางเลือกของหลังที่ i ไม่เข้าหรือเข้า

7
20 50 30 10 60 40 30

0 20 50 50 60 110 110 140

ดูช่อง 3 ได้ 50 ไม่ใช่ 20 + 30 เพราะเข้าหลังที่ 2 หลังเดียวได้มากกว่า ช่อง 5 ได้ 110 จากการเข้าหลังที่ 5 ต่อจาก best[3] คือ 50 + 60 ค่าในตารางไม่ลดลงเลย เพราะมีบ้านให้เลือกมากขึ้นก็ไม่มีทางได้น้อยลง ส่วนว่าหลังไหนบ้างที่ถูกเลือก ตารางนี้ยังไม่บอก หน้า 24.5 จะย้อนหาให้

สังเกตว่าสถานะไม่ได้จำว่าหลังที่ i - 1 ถูกเข้าหรือเปล่า ไม่จำเป็นต้องจำ เพราะสูตรแยกเป็นสองกรณีไว้ให้แล้ว และทางที่เข้าหลังที่ i กระโดดไปอ่าน best[i - 2] ซึ่งไม่เกี่ยวกับหลังที่ i - 1 เลย

ผลรวมช่วงย่อยมากสุด

ร้านขายน้ำปั่นจดกำไรรายวัน วันไหนขาดทุนก็จดเป็นค่าติดลบ เจ้าของอยากรู้ว่าช่วงวันติดกันช่วงไหนที่กำไรรวมมากที่สุด ต้องเลือกอย่างน้อยหนึ่งวัน กำไร 8 วันคือ -3 5 -2 4 -6 3 2 -1

ลองนิยามแบบบ้านติดกัน "best[i] คือช่วงที่ดีที่สุดในวันที่ 1 ถึง i" จะติดตอนหาความสัมพันธ์ ถ้าวันที่ i จะต่อกับช่วงก่อนหน้า ช่วงนั้นต้องจบที่วัน i - 1 พอดี แต่ best[i - 1] อาจเป็นช่วงที่จบก่อนหน้านั้นไปไกล ต่อกันไม่ได้ สถานะเก็บข้อมูลไม่พอตามที่เตือนไว้ในหน้า 24.2 จึงนิยามให้แคบลง

1. สถานะ ending[i] คือกำไรรวมมากที่สุดของช่วงที่ จบที่วัน i พอดี
2. ความสัมพันธ์ ช่วงที่จบที่วัน i มีสองแบบ คือมีแค่วัน i วันเดียว ได้ a[i] หรือต่อจากช่วงที่จบที่วัน i - 1 ซึ่งดีที่สุดคือ ending[i - 1] ได้ ending[i - 1] + a[i] เลือกค่าที่มากกว่า พูดง่ายๆ คือถ้าช่วงก่อนหน้าติดลบ ทิ้งมันแล้วเริ่มใหม่ที่วัน i
3. กรณีฐาน ending[1] = a[1]
4. เติม i จาก 2 ถึง N คำตอบคือ ค่ามากสุดของทุกช่อง เพราะช่วงที่ดีที่สุดจบที่วันไหนก็ได้

วิธีนี้มีชื่อว่า Kadane's algorithm ตามชื่อคนที่คิด

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

int main()
{
    int n;
    cin >> n;
    vector<long long> profit(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> profit[i];
    }
    vector<long long> ending(n + 1); // (1)!
    ending[1] = profit[1];
    long long answer = ending[1];
    for (int i = 2; i <= n; i++) {
        ending[i] = max(profit[i], ending[i - 1] + profit[i]); // (2)!
        answer = max(answer, ending[i]); // (3)!
    }
    for (int i = 1; i <= n; i++) {
        cout << ending[i] << (i < n ? ' ' : '\n');
    }
    cout << "best = " << answer << '\n';
    return 0;
}

1. เป็น long long เพราะในโจทย์จริง N เป็นแสนและกำไรวันละ 10⁹ ผลรวมเกิน int
2. ต่อจากช่วงเดิม หรือเริ่มใหม่ที่วันนี้
3. เก็บค่ามากสุดไปพร้อมกับเติมตาราง ไม่ต้องวนหาใหม่ทีหลัง

8
-3 5 -2 4 -6 3 2 -1

-3 5 3 7 1 4 6 5
best = 7

วันที่ 2 ช่วงก่อนหน้าติดลบ จึงเริ่มใหม่ได้ 5 วันที่ 3 ต่อได้ 5 - 2 = 3 วันที่ 4 ต่อได้ 3 + 4 = 7 ซึ่งคือวันที่ 2 ถึง 4 วันที่ 6 ช่วงก่อนหน้าคือ 1 ยังเป็นบวก จึงต่อได้ 1 + 3 = 4 แทนที่จะเริ่มใหม่ที่ 3 ช่องที่มากที่สุดคือช่อง 4 ไม่ใช่ช่องสุดท้าย ถ้าตอบ ending[8] จะได้ 5 ซึ่งผิด

เร็วขึ้นแค่ไหน

วิธีตรงไปตรงมาของบ้านติดกันคือ recursion ที่ลองทั้งเข้าและไม่เข้าทุกหลังโดยไม่จด ส่วนช่วงย่อยมากสุดคือลองทุกจุดเริ่ม แล้วบวกสะสมไปทุกจุดจบ ซึ่งเป็น O(N²) วัดบนเครื่องเดียวกับหน้า 24.1 รันแบบละ 5 ครั้ง เงินในบ้านกับกำไรรายวันสร้างด้วยสูตรในโปรแกรม เงินอยู่ระหว่าง 1 ถึง 100 กำไรอยู่ระหว่าง -1000 ถึง 1000

recursion ของบ้านติดกันแตกสองกิ่งต่อหลัง เวลาจึงโตแบบเดียวกับฟีโบนัชชี บ้านแค่ 40 หลังก็ใช้ราวสองวินาทีครึ่ง ส่วน DP เดินบ้านสิบล้านหลังได้ในไม่ถึงหนึ่งในสิบวินาที วิธีทุกคู่ของช่วงย่อยที่ N เป็นแสนต้องบวกราว 5 × 10⁹ ครั้ง เกินหนึ่งวินาทีไปไกลแม้ใช้ -O2

ลองทำให้พัง

แบบที่ 1 เริ่มคำตอบที่ 0

ในโปรแกรม kadane เขียน long long answer = 0; เพราะชินกับการหาค่ามากสุดของจำนวนบวก ข้อมูลตัวอย่างยังได้ 7 ถูก แต่ป้อนสัปดาห์ที่ขาดทุนทุกวัน

4
-5 -2 -8 -3

-5 -2 -8 -3
best = 0

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

แบบที่ 2 ตอบช่องสุดท้าย

เคยชินกับบ้านติดกันที่ตอบ best[N] จึงพิมพ์ ending[n] แทน answer ข้อมูลตัวอย่างได้ 5 แทน 7 เพราะ ending[8] คือช่วงที่บังคับจบวันที่ 8 ตำแหน่งของคำตอบขึ้นกับนิยามของสถานะ ขั้นที่ 4 ในหน้า 24.2 จึงต้องคิดทุกครั้ง ไม่ใช่ตอบช่องสุดท้ายโดยอัตโนมัติ

สรุป

• บ้านติดกัน best[i] = max(best[i - 1], best[i - 2] + a[i]) สองทางคือไม่เข้าหรือเข้าหลังที่ i
• ใช้ช่อง 0 เป็นกรณีฐาน "ยังไม่มีข้อมูล" ช่วยให้ไม่ต้องเขียนกรณีพิเศษตอนต้นแถว
• ช่วงย่อยมากสุดนิยาม ending[i] เป็นช่วงที่จบที่ i พอดี ต่อจากช่วงเดิมหรือเริ่มใหม่ แล้วตอบค่ามากสุดของทุกช่อง
• คำตอบเริ่มจากช่องจริงของตาราง ไม่ใช่ 0 เพราะข้อมูลติดลบทั้งหมดได้
• ทั้งสองข้อเป็น O(N) เทียบกับ recursion ที่โตแบบทวีคูณ และวิธีทุกคู่ที่เป็น O(N²)