Giả sử chúng ta có số người chẵn n đứng quanh một vòng tròn và mỗi người bắt tay với người khác, như vậy sẽ có n/2 lần bắt tay tổng cộng. Chúng ta phải tìm số cách các lần bắt tay này có thể xảy ra sao cho không có lần bắt tay nào cắt nhau. Kết quả có thể rất lớn nên trả về kết quả mod 10^9 + 7.
Vì vậy, nếu đầu vào là n = 2, đầu ra sẽ là 1
Để giải quyết, chúng ta sẽ làm theo các bước:
m := 10^9 + 7
Định nghĩa mảng dp kích thước (n+1)
dp[0] := 1
Khởi tạo i := 0, khi i <= n, cập nhật i := i + 2, làm:
Khởi tạo j := 0, khi j <= i-2, cập nhật j := j + 2, làm:
dp[i] := dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)
dp[i] := dp[i] mod m
Trả về dp[n] mod m
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
#include <bits/stdc++.h> using namespace std; const int m = 1e9+7; typedef long long int lli; class Solution { public: int numberOfWays(int n) { vector <lli> dp(n+1); dp[0] = 1; for(int i = 0; i <= n; i+=2 ){ for(int j =0 ; j <= i-2; j+=2){ dp[i] += (dp[j]%m * dp[i-2-j]%m)%m; dp[i]%=m; } } return dp[n]%m; } }; main(){ Solution ob; cout << (ob.numberOfWays(2)); }Đầu vào
2
Đầu ra
1