Dice Roll Simulation ใน C++: นับลำดับการทอยลูกเต๋าที่ไม่ซ้ำภายใต้เงื่อนไข

โจทย์

ลูกเต๋า 6 หน้า ทอย n ครั้ง หน้า i ไม่อนุญาตให้ออกติดกันเกิน rollMax[i] ครั้ง (1-indexed) หาจำนวนลำดับที่เป็นไปได้

ตัวอย่าง: n=2, rollMax=[1,1,2,2,2,3] → 34 (จาก 36 ลบ (1,1) และ (2,2) ที่ห้ามติดกัน)

แนวคิด: DP + Memoization (Top-down)

State: dfs(dieLeft, lastFace, currLen) = จำนวนวิธีทอยอีก dieLeft ครั้ง โดยหน้าล่าสุดคือ lastFace ติดกันมา currLen ครั้ง

ขั้นตอน

1. สร้าง 3D array dp[n+1][6][16] ใส่ -1 (max rollMax = 15)
2. ฟังก์ชัน dfs(dieLeft, last, currLen):
   • ถ้า dieLeft == 0 → return 1
   • ถ้า dp[dieLeft][last][currLen] != -1 → return ค่าที่เก็บ
   • ans = 0
   • ลูปหน้า i = 0 ถึง 5:
     • ถ้า i == last && currLen == rollMax[i] → ข้าม (ห้ามติดต่อกันเกิน)
     • nextLen = (i == last) ? currLen + 1 : 1
     • ans = (ans + dfs(dieLeft-1, i, nextLen)) % MOD
   • เก็บและคืน dp[dieLeft][last][currLen] = ans
3. เรียก dfs(n, 0, 0) (last=0, currLen=0 เป็นค่าเริ่มต้น dummy)

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

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

const int MOD = 1e9 + 7;

class Solution {
    int dfs(int dieLeft, int last, int currLen, vector<int>& rollMax, 
            vector<vector<vector<int>>>& dp) {
        if (dieLeft == 0) return 1;
        if (dp[dieLeft][last][currLen] != -1) return dp[dieLeft][last][currLen];
        
        long long ans = 0;
        for (int i = 0; i < 6; i++) {
            if (i == last && currLen == rollMax[i]) continue;
            int nextLen = (i == last) ? currLen + 1 : 1;
            ans = (ans + dfs(dieLeft - 1, i, nextLen, rollMax, dp)) % MOD;
        }
        return dp[dieLeft][last][currLen] = ans;
    }
    
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(6, vector<int>(16, -1)));
        return dfs(n, 0, 0, rollMax, dp);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,1,2,2,2,3};
    cout << ob.dieSimulator(2, v); // 34
    return 0;
}

อินพุต / เอาต์พุต

Input: 2 [1,1,2,2,2,3]

Output: 34

ความซับซ้อน

• Time: O(n × 6 × 15 × 6) = O(n) - state ประมาณ n×6×15 แต่ละ state ลูป 6 รอบ
• Space: O(n × 6 × 16)