สมมติว่าเรามี n จุดบนเส้น โดยที่จุด ith (จาก 0 ถึง n-1) อยู่ที่ตำแหน่ง x =i เราต้องหาจำนวนวิธีที่เราสามารถวาด k ส่วนต่าง ๆ ของเส้นที่ไม่ทับซ้อนกันได้อย่างแม่นยำ ส่วนครอบคลุมสองจุดขึ้นไป จุดสิ้นสุดของแต่ละส่วนของเส้นตรงต้องมีพิกัดเชิงปริพันธ์ ส่วนของเส้นตรง k ไม่จำเป็นต้องครอบคลุม n จุดที่กำหนดทั้งหมด และสามารถแบ่งปันจุดปลายได้ หากคำตอบมีขนาดใหญ่เกินไป ให้คืนค่า mod ผลลัพธ์ 10^9+7
ดังนั้น ถ้าอินพุตเป็นเหมือน n =4 k =2 ผลลัพธ์จะเป็น 5 เพราะเราสร้างความเป็นไปได้ได้ห้าอย่าง [(0 ถึง 2),(2 ถึง 3)], [(0 ถึง 1),(1 ถึง 3)], [(0 ถึง 1),(2 ถึง 3)], [(1 ถึง 2),(2 ถึง 3)] และ [(0 ถึง 1),(1 ถึง 2)]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ม :=10^9 + 7
- n :=n - 1
- กำหนดฟังก์ชัน dp() นี้จะใช้เวลา i, ครอบคลุม, j
- ถ้าฉันเหมือนกับ n แล้ว
- คืนค่า จริง ถ้า j เหมือนกับ k มิฉะนั้น เท็จ
- ถ้า j> k แล้ว
- เช่น :=dp(i + 1, เท็จ, j) + dp(i + 1, จริง, j + 1)
- ถ้าครอบคลุมเป็นจริงแล้ว
- ans :=ans + dp(i + 1, True, j)
- ส่งคืน mod m
- จากวิธีหลักส่งคืน dp(0, False, 0)
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(n, k): m = 10 ** 9 + 7 n -= 1 def dp(i, covered, j): if i == n: return j == k if j > k: return 0 ans = dp(i + 1, False, j) + dp(i + 1, True, j + 1) if covered: ans += dp(i + 1, True, j) return ans % m return dp(0, False, 0) n = 4 k = 2 print(solve(n, k))
อินพุต
4, 2
ผลลัพธ์
5
