นับวิธีการจัดส่งและรับสินค้าที่ถูกต้องใน C++

คำอธิบายโจทย์

มี n คำสั่งซื้อ แต่ละคำสั่งมีการรับ (Pickup) และส่ง (Delivery) ต้องนับจำนวนลำดับที่ถูกต้องที่ delivery[i] ต้องอยู่หลัง pickup[i] เสมอ ผลลัพธ์ modulo 10^9+7

ตัวอย่าง

n = 2 → Output: 6

ลำดับที่ถูกต้อง: (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1), (P2,D2,P1,D1)

วิธีแก้ปัญหา

ใช้ Dynamic Programming แบบ Memoization:

• State: solve(inPickup, left, i, j)
  • inPickup: จำนวน pickup ที่ยังไม่มี delivery
  • left: จำนวนคำสั่งที่ยังไม่เริ่ม
  • i: pickup ที่เหลือ, j: delivery ที่เหลือ
• Transition:
  • ทำ pickup ใหม่: left * solve(inPickup+1, left-1, i-1, j)
  • ทำ delivery: inPickup * solve(inPickup-1, left, i, j-1) (ต้องมี j > i)
• Base case: i=0, j=0 → 1

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int MOD = 1e9 + 7;
const int N = 550;
int dp[N+5][N+5];

lli add(lli a, lli b) { return ((a%MOD)+(b%MOD))%MOD; }
lli mul(lli a, lli b) { return ((a%MOD)*(b%MOD))%MOD; }

class Solution {
public:
    void pre() {
        for(int i=0;i 0) ret = add(ret, mul(left, solve(inPickup+1, left-1, i-1, j)));
        if(j > i) ret = add(ret, mul(inPickup, solve(inPickup-1, left, i, j-1)));
        
        return dp[i][j] = ret;
    }
    
    int countOrders(int n) {
        pre();
        return solve(0, n, n, n);
    }
};

int main() {
    Solution ob;
    cout << ob.countOrders(2);
    return 0;
}

อินพุต

2

เอาต์พุต

6