สมมติว่าเรามีจำนวนคนเป็นเลขคู่ n คน ยืนวงกลม และแต่ละคนจับมือกับอีกคนหนึ่ง จะมีการจับมือทั้งหมด n/2 ครั้ง เราต้องหาจำนวนวิธีที่การจับมือเหล่านี้อาจเกิดขึ้น โดยที่ไม่มีการจับมือใดทับซ้อนกัน คำตอบอาจใหญ่มาก ดังนั้นให้คืนคำตอบแบบ modulo 10⁹ + 7
ดังนั้น หากอินพุทคือ n = 2 ผลลัพธ์จะเป็น 1
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
m := 10⁹ + 7
กำหนดอาเรย์ dp ขนาด (n+1)
dp[0] := 1
for i := 0 ถึง n ขึ้นทีละ 2:
for j := 0 ถึง i-2 ขึ้นทีละ 2:
dp[i] := dp[i] + (dp[j] mod m * dp[i - 2 - j] mod m)
dp[i] := dp[i] mod m
คืนค่า dp[n] mod m
ตัวอย่างโค้ด
#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 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;
}
};
int main() {
Solution ob;
cout << (ob.numberOfWays(2));
return 0;
}
อินพุต
2
เอาต์พุต
1
