[0]zero-index clytie0x/zero-index

24.2 วิธีคิด DP สี่ขั้น

หน้า 24.1 ได้สูตรทอนเหรียญมาจากการคิดว่า "เหรียญแรกเป็นอะไรได้บ้าง" แต่พอเจอโจทย์ใหม่ น้องจะคิดสูตรแบบนั้นเองได้ยังไง หน้านี้แบ่งการคิดเป็นสี่ขั้นที่ทำบนกระดาษก่อนเขียนโค้ดทุกครั้ง ทำครบสี่ขั้นแล้ว โค้ดแทบจะเขียนตัวเอง แล้วต่อด้วยสองเรื่องที่มากับ DP เสมอ คือคำตอบที่ใหญ่จนต้อง mod และการประมาณเวลาจากจำนวนสถานะ

โจทย์บันไดที่มีขั้นพัง

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

ลองกับบันได 10 ขั้นที่ขั้น 4 กับ 7 พัง จะข้ามขั้น 4 ได้ต้องก้าว 2 ขั้นจากขั้น 3 ไปขั้น 5 ข้ามขั้น 7 ได้ต้องก้าวจากขั้น 6 ไปขั้น 8 ทุกวิธีจึงต้องผ่านขั้น 3 5 6 และ 8 จากพื้นไปขั้น 3 มี 3 วิธี (1+1+1, 1+2, 2+1) จากขั้น 8 ไปขั้น 10 มี 2 วิธี รวม 3 × 2 = 6 วิธี นับด้วยมือได้เพราะบันไดสั้น ถ้าบันไดยาวแสนขั้นต้องให้โปรแกรมนับ

ขั้นที่ 1 นิยามสถานะ

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

สถานะของโจทย์บันได

ways[i] คือจำนวนวิธีเดินจากพื้นไปหยุดที่ขั้น i โดยไม่เหยียบขั้นพัง

สถานะที่ดีมีสองอย่าง อย่างแรก คำตอบของโจทย์ต้องเป็นช่องใดช่องหนึ่ง หรือหาได้ง่ายจากตาราง ข้อนี้คำตอบคือ ways[N] อย่างที่สอง แต่ละช่องต้องคำนวณได้จากช่องอื่นที่เล็กกว่า โดยไม่ต้องรู้ว่าก่อนหน้านั้นเดินมายังไง ถ้าน้องต้องรู้ประวัติการเดินด้วยถึงจะคำนวณต่อได้ แปลว่าสถานะเก็บข้อมูลไม่พอ ต้องเพิ่มข้อมูลเข้าไปในสถานะ ซึ่งจะเห็นในแบบฝึกหัดข้อท้ายๆ

ขั้นที่ 2 หาความสัมพันธ์

หาว่าช่อง i คำนวณจากช่องไหน วิธีคิดที่ใช้ได้เกือบทุกข้อคือ ดูการตัดสินใจครั้งสุดท้าย จะไปหยุดที่ขั้น i ก้าวสุดท้ายต้องเป็นก้าว 1 ขั้นจากขั้น i - 1 หรือก้าว 2 ขั้นจากขั้น i - 2 อย่างใดอย่างหนึ่ง

ways[i] = 0                          ถ้าขั้น i พัง
ways[i] = ways[i - 1] + ways[i - 2]  ถ้าไม่พัง

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

ขั้นที่ 3 กรณีฐาน

ช่องที่สูตรใช้ไม่ได้ ต้องกำหนดค่าเอง ข้อนี้คือขั้น 0 กับขั้น 1 เพราะสูตรจะอ่านขั้นติดลบ

  • ways[0] = 1 ยืนอยู่บนพื้นแล้วมีหนึ่งวิธี คือไม่ต้องก้าว ฟังดูแปลก แต่ตรวจได้ ways[2] ต้องเป็น 2 (1+1 กับ 2) ซึ่งได้จาก ways[1] + ways[0] = 1 + 1 ถ้าให้ ways[0] เป็น 0 จะผิดทันที ดูในส่วนลองทำให้พัง
  • ways[1] มาจากขั้น 0 ได้ทางเดียว จึงเท่ากับ ways[0] ถ้าขั้น 1 ไม่พัง

ขั้นที่ 4 ลำดับการเติมและคำตอบสุดท้าย

ดูจากสูตรว่าช่อง i อ่านช่องไหน แล้วเลือกลำดับที่ช่องเหล่านั้นเสร็จก่อน ข้อนี้อ่าน i - 1 กับ i - 2 จึงเติมจาก 1 ขึ้นไปถึง N แล้วตอบ ways[N] สองขั้นนี้รวมกันเพราะคิดคู่กันเสมอ ตำแหน่งของคำตอบไม่จำเป็นต้องเป็นช่องสุดท้าย หน้า 24.4 มีโจทย์ที่คำตอบคือค่ามากสุดของทุกช่อง

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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<bool> broken(n + 1, false);
    for (int j = 0; j < k; j++) {
        int step;
        cin >> step;
        broken[step] = true;
    }
    vector<long long> ways(n + 1); // (1)!
    ways[0] = 1; // (2)!
    for (int i = 1; i <= n; i++) { // (3)!
        if (broken[i]) {
            ways[i] = 0;
        } else if (i == 1) { // (4)!
            ways[i] = ways[i - 1];
        } else {
            ways[i] = ways[i - 1] + ways[i - 2];
        }
    }
    for (int i = 0; i <= n; i++) { // (5)!
        cout << ways[i] << (i < n ? ' ' : '\n');
    }
    return 0;
}
  1. ขั้นที่ 1 ตารางหนึ่งช่องต่อหนึ่งสถานะ ช่อง 0 ถึง N
  2. ขั้นที่ 3 กรณีฐาน
  3. ขั้นที่ 4 เติมจากน้อยไปมาก
  4. ขั้นที่ 3 อีกกรณี ขั้น 1 มาจากขั้น 0 ได้ทางเดียว ไม่มีขั้น -1 ให้อ่าน
  5. พิมพ์ทั้งตารางให้ตรวจกับมือได้ โปรแกรมส่ง grader พิมพ์แค่ ways[n]
10 2
4 7

1 1 2 3 0 3 3 0 3 3 6

ตัวสุดท้ายคือ 6 ตรงกับที่นับด้วยมือ ช่อง 4 กับ 7 เป็น 0 ช่อง 5 ได้ 3 เพราะมาจากขั้น 3 ได้ทางเดียว ส่วนบรรทัด cout ใช้ ? : จากหน้า 3.4 เพื่อพิมพ์ช่องว่างระหว่างตัวเลข แต่ไม่พิมพ์ช่องว่างเกินท้ายบรรทัด

ทั้งสี่ขั้นใช้กับโจทย์ทอนเหรียญในหน้า 24.1 ได้เหมือนกัน

ขั้นบันไดขั้นพังทอนเหรียญ 1 3 4
สถานะways[i] จำนวนวิธีไปหยุดที่ขั้น idp[x] จำนวนเหรียญน้อยสุดที่รวมได้ x บาท
ความสัมพันธ์ก้าวสุดท้าย 1 หรือ 2 ขั้น บวกกันเหรียญแรก 1 3 หรือ 4 บาท เอาค่าน้อยสุด
กรณีฐานways[0] = 1dp[0] = 0
ลำดับและคำตอบi จาก 1 ถึง N ตอบ ways[N]x จาก 1 ถึง X ตอบ dp[X]

ถ้าอยากเขียนแบบ top-down ก็ใช้สี่ขั้นเดิม สถานะคือพารามิเตอร์ของฟังก์ชัน ความสัมพันธ์คือการเรียกตัวเอง กรณีฐานคือ if ที่คืนค่าทันที ส่วนลำดับการเติม recursion จัดให้เอง

คำตอบใหญ่เกิน long long

ตารางนี้โตเร็วแบบฟีโบนัชชี ลองโปรแกรมที่พิมพ์แค่คำตอบกับบันได 100 ขั้นที่ไม่มีขั้นพัง

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<bool> broken(n + 1, false);
    for (int j = 0; j < k; j++) {
        int step;
        cin >> step;
        broken[step] = true;
    }
    vector<long long> ways(n + 1);
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (broken[i]) {
            ways[i] = 0;
        } else if (i == 1) {
            ways[i] = ways[i - 1];
        } else {
            ways[i] = ways[i - 1] + ways[i - 2];
        }
    }
    cout << ways[n] << '\n';
    return 0;
}

100 0

1298777728820984005

ได้เลขบวกสิบเก้าหลักที่ดูน่าเชื่อ แต่คำตอบจริงคือ 573147844013817084101 ยาว 21 หลัก ล้น long long ไปตั้งแต่ขั้นที่ 92 แบบเดียวกับ fib(93) ในหน้า 9.3 ตอนนั้นยังได้ค่าติดลบให้เห็นว่าผิด แต่ครั้งนี้บวกต่อไปอีกหลายขั้นจนค่าที่ล้นวนกลับมาเป็นบวก จึงสังเกตไม่ออกถ้าไม่คำนวณขนาดก่อน โจทย์นับวิธีจึงสั่งให้ตอบเป็นเศษจากการหารด้วย 1000000007 ตามหน้า 12.1 และใช้กฎเดียวกัน คือเก็บแค่เศษตั้งแต่ระหว่างทาง

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

const long long MOD = 1000000007; // (1)!

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<bool> broken(n + 1, false);
    for (int j = 0; j < k; j++) {
        int step;
        cin >> step;
        broken[step] = true;
    }
    vector<long long> ways(n + 1);
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (broken[i]) {
            ways[i] = 0;
        } else if (i == 1) {
            ways[i] = ways[i - 1];
        } else {
            ways[i] = (ways[i - 1] + ways[i - 2]) % MOD; // (2)!
        }
    }
    cout << ways[n] << '\n';
    return 0;
}
  1. แบบ #define MOD ในหน้า 12.1 แต่ใช้ const ซึ่งเป็นตัวแปรที่มีชนิดและห้ามแก้ค่า ภาษา C++ นิยมแบบนี้มากกว่า ถ้าเผลอเขียน MOD = 5; compiler จะฟ้อง
  2. สองช่องที่บวกกันมีค่าน้อยกว่า MOD อยู่แล้ว ผลบวกไม่เกินสองพันล้าน ไม่ล้น long long แน่นอน mod ทันทีหลังบวกทุกครั้ง
100 0

782204094

573147844013817084101 หารด้วย 1000000007 เหลือเศษ 782204094 พอดี โปรแกรมนี้อ่านข้อมูลได้มาก (ขั้นพังได้เป็นแสนขั้น) จึงเปิด ios::sync_with_stdio(false) ตามหน้า 15.3 ด้วย

ความซับซ้อนคือจำนวนสถานะคูณงานต่อสถานะ

DP คำนวณแต่ละสถานะครั้งเดียว เวลาทั้งหมดจึงประมาณได้ก่อนเขียนจากสองตัวเลข

สูตรประมาณเวลา

เวลาของ DP = จำนวนสถานะ × งานที่ทำต่อหนึ่งสถานะ

บันไดข้างบนมี N + 1 สถานะ แต่ละสถานะบวกสองค่า จึงเป็น O(N) ลองทำให้งานต่อสถานะมากขึ้น ถ้าแต่ละก้าวขึ้นได้ 1 ถึง K ขั้น ก้าวสุดท้ายมาได้จาก K ขั้นก่อนหน้า ต้องบวก K ค่าต่อหนึ่งสถานะ

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

const int MOD = 1000000007;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> ways(n + 1);
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        long long total = 0;
        for (int j = 1; j <= k && j <= i; j++) {
            total += ways[i - j];
        }
        ways[i] = total % MOD;
    }
    cout << ways[n] << '\n';
    return 0;
}

10 3

274

ตารางเก็บเป็น int ได้เพราะทุกช่องน้อยกว่า MOD แต่ตัวแปร total ต้องเป็น long long เพราะบวก K ค่าที่เกือบถึง MOD ก่อนค่อย mod ตอนท้าย K ไม่เกินพันก็ไม่ถึง 1013 สถานะ N + 1 ตัว งาน K ต่อตัว รวม O(NK) วัดบนเครื่องเดียวกับหน้า 24.1 รันแบบละ 5 ครั้ง

NKN × KCode::Blocks (-Wall)-O2
100000022 × 1060.012 วินาที0.007 วินาที
100000101060.002 วินาที0.001 วินาที
1000001001070.017 วินาที0.004 วินาที
10000010001080.175 วินาที0.035 วินาที
100000010001091.888 วินาที (5 รอบอยู่ระหว่าง 1.719 ถึง 2.169)0.368 วินาที

N × K เพิ่มสิบเท่า เวลาก็เพิ่มราวสิบเท่าตาม ประมาณจาก N × K แล้วเทียบกับหลักในหน้า 18.2 ได้เลยตั้งแต่ก่อนเขียน แถวสุดท้ายแบบ -O2 เร็วกว่าที่คาด เพราะลูปบวกต่อเนื่องเป็นงานที่ compiler เร่งได้มาก แต่ถ้า N เพิ่มเป็นสิบล้านก็เกินแน่นอน

เทียบกับ recursion ตรงๆ ของโจทย์บันไดที่ไม่จดคำตอบ

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

vector<char> broken;

long long count_ways(int i)
{
    if (broken[i]) {
        return 0;
    }
    if (i <= 1) {
        return 1;
    }
    return count_ways(i - 1) + count_ways(i - 2);
}

int main()
{
    int n, k;
    cin >> n >> k;
    broken = vector<char>(n + 1, false);
    for (int j = 0; j < k; j++) {
        int step;
        cin >> step;
        broken[step] = true;
    }
    cout << count_ways(n) << '\n';
    return 0;
}

10 2
4 7

6

ได้ 6 ตรงกับตาราง จับเวลาเฉพาะการเรียก count_ways(n) ด้วย clock() แบบหน้า 9.3 รันแบบละ 5 ครั้ง บันได 30 ขั้นใช้ 0.005 วินาทีแบบ Code::Blocks และ 0.001 วินาทีแบบ -O2 บันได 40 ขั้นใช้ 0.800 วินาที (5 รอบอยู่ระหว่าง 0.721 ถึง 0.968) กับ 0.172 วินาที ส่วนแบบตารางเดินบันไดล้านขั้นในแถวแรกเสร็จในราวหนึ่งในร้อยวินาที โปรแกรมนี้เก็บขั้นพังเป็น vector<char> ไม่ใช่ vector<bool> แบบโปรแกรม broken-stairs เพราะ recursion อ่าน broken[i] ทุกครั้งที่เรียก สามร้อยกว่าล้านครั้ง ถ้าใช้ vector<bool> บันได 40 ขั้นแบบ Code::Blocks ช้าลงเป็น 5.245 วินาที ตามเหตุผลในหน้า 23.4

ลองทำให้พัง

แบบที่ 1 กรณีฐานเป็น 0

ในโปรแกรม broken-stairs คิดว่ายืนเฉยๆ ไม่ได้ก้าว ก็ไม่น่านับเป็นวิธี จึงเปลี่ยนเป็น ways[0] = 0; ป้อนข้อมูลเข้าเดิม

0 0 0 0 0 0 0 0 0 0 0

ศูนย์ทั้งตาราง เพราะทุกช่องเป็นผลบวกของช่องก่อนหน้า ถ้าต้นทางเป็น 0 ทุกอย่างก็เป็น 0 กรณีฐานผิดช่องเดียวทำให้ทั้งตารางผิด วิธีตรวจคือคำนวณช่องเล็กๆ ด้วยมือ เช่น ways[2] ต้องเป็น 2 แล้วดูว่ากรณีฐานพาไปถึงค่านั้นไหม

แบบที่ 2 บวกหลายค่าใน int ก่อน mod

ในโปรแกรม k-steps เห็นว่าตารางเป็น int ก็เลยประกาศ total เป็น int ด้วย

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

const int MOD = 1000000007;

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> ways(n + 1);
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        int total = 0;
        for (int j = 1; j <= k && j <= i; j++) {
            total += ways[i - j];
        }
        ways[i] = total % MOD;
    }
    cout << ways[n] << '\n';
    return 0;
}

100 3

961558590

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

สรุป

  • ก่อนเขียน DP ทำสี่ขั้น นิยามสถานะเป็นประโยคเต็ม หาความสัมพันธ์จากการตัดสินใจครั้งสุดท้าย กำหนดกรณีฐาน และเลือกลำดับการเติมพร้อมตำแหน่งคำตอบ
  • โจทย์นับวิธี กลุ่มที่บวกกันต้องไม่ซ้อนกันและครอบคลุมครบ
  • กรณีฐานผิดช่องเดียว ทั้งตารางผิดตาม ตรวจด้วยช่องเล็กๆ ที่นับมือได้
  • คำตอบที่โตแบบฟีโบนัชชีล้น long long ตั้งแต่ราวช่อง 92 ให้ mod 1000000007 ทุกครั้งที่บวก
  • เวลาของ DP = จำนวนสถานะ × งานต่อสถานะ ก้าวได้ถึง K ขั้นเป็น O(NK)