Đếm số cách lấy/hàng giao hợp lệ trong C++

Cho n đơn hàng, mỗi đơn có dịch vụ lấy hàng (pickup) và giao hàng (delivery). Cần đếm tất cả các chuỗi hợp lệ sao cho delivery[i] luôn sau pickup[i]. Kết quả lấy modulo 10^9 + 7.

Ví dụ với n = 2, đầu ra là 6. Các chuỗi hợp lệ: (P1,P2,D1,D2), (P1,P2,D2,D1), (P1,D1,P2,D2), (P2,P1,D1,D2), (P2,P1,D2,D1), (P2,D2,P1,D1). Chuỗi (P1,D2,P2,D1) không hợp lệ vì Pickup 2 sau Delivery 2.

Giải pháp

Sử dụng quy hoạch động với trạng thái (inPickup, left, i, j):

inPickup: số đơn đang chờ giao (đã lấy chưa giao)
left: số đơn chưa lấy
i: số pickup còn lại
j: số delivery còn lại

Cơ sở: nếu i=0 và j=0 trả về 1

Chuyển trạng thái:

Nếu i > 0: thực hiện pickup, inPickup+1, left-1, i-1
Nếu j > i: thực hiện delivery, inPickup-1, left, j-1

Sử dụng memoization với mảng dp[N+5][N+5].

Ví dụ mã C++

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

typedef long long int lli; 
const int m = 1e9 + 7; 
const int N = 550; 
int dp[N + 5][N + 5]; 

lli add(lli a, lli b) { 
    return ((a % m) + (b % m)) % m; 
} 

lli mul(lli a, lli b) { 
    return ((a % m) * (b % m)) % m; 
} 

class Solution { 
public: 
    void pre() { 
        for (int i = 0; i < N; i++) 
            for (int j = 0; j < N; j++) 
                dp[i][j] = -1; 
    } 
    
    int solve(int inPickup, int left, int i, int j) { 
        if (i == 0 && j == 0) return 1; 
        if (dp[i][j] != -1) return dp[i][j]; 
        
        int ret = 0; 
        if (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; 
}

Đếm số cách lấy/hàng giao hợp lệ trong C++

Giải pháp

Ví dụ mã C++

Đầu vào

Đầu ra