ปัญหา: กำหนด Binary Matrix และ k ต้องตัด Matrix เป็น k ชิ้น โดย:
- เลือกทิศทาง: Vertical หรือ Horizontal
- เลือก Index ตัด (Vertical: ตัดแนวตั้ง, Horizontal: ตัดแนวนอน)
- Vertical Cut: ทิ้งซ้าย, ตัดขวาต่อ | Horizontal Cut: ทิ้งบน, ตัดล่างต่อ
- แต่ละชิ้นต้องมี 1 อย่างน้อย 1 ตัว
หาจำนวนวิธี Mod 10⁹+7
อัลกอริทึม: DP + Prefix Sum (2D)
- สร้าง 2D Prefix Sum `counts[i][j]` = จำนวน 1 ใน Submatrix (i,j) ถึง (m-1,n-1) (Bottom-Right)
- DP Function `f(x, y, c)` = วิธีตัด Submatrix (x,y) ถึง Bottom-Right เป็น c+1 ชิ้น
- Base Case: c=0 → Return 1 ถ้ามี 1 อย่างน้อย 1 ตัว
- Transition: ลอง Vertical Cuts (i=x+1..m-1) และ Horizontal Cuts (j=y+1..n-1) ที่แบ่ง 1 ได้ทั้งสองข้าง
- Memoization ด้วย LRU Cache หรือ Dictionary
การติดตั้ง
from collections import defaultdict
from functools import lru_cache
class Solution:
def solve(self, matrix, k):
MOD = 10**9 + 7
m, n = len(matrix), len(matrix[0])
# 2D Prefix Sum (Bottom-Right)
counts = defaultdict(int)
for i in range(m-1, -1, -1):
for j in range(n-1, -1, -1):
counts[(i, j)] = (counts[(i+1, j)] + counts[(i, j+1)]
- counts[(i+1, j+1)] + matrix[i][j])
@lru_cache(None)
def f(x, y, c):
total_ones = counts[(x, y)]
if c == 0:
return 1 if total_ones > 0 else 0
ans = 0
# Vertical Cuts (Cut columns, keep right part)
for i in range(x+1, m):
left_ones = counts[(x, y)] - counts[(i, y)]
if 0 < left_ones < total_ones:
ans = (ans + f(i, y, c-1)) % MOD
# Horizontal Cuts (Cut rows, keep bottom part)
for j in range(y+1, n):
top_ones = counts[(x, y)] - counts[(x, j)]
if 0 < top_ones < total_ones:
ans = (ans + f(x, j, c-1)) % MOD
return ans
return f(0, 0, k-1)
# Test
ob = Solution()
matrix = [
[1, 1, 0],
[1, 0, 1],
[1, 1, 1]
]
k = 2
print(ob.solve(matrix, k)) # Output: 4
คำอธิบาย
Prefix Sum (Bottom-Right): `counts[i][j]` = 1's ใน Rectangle (i,j) ถึง (m-1,n-1) คำนวณ O(mn)
DP State: `f(x, y, c)` = วิธีตัด Submatrix เริ่ม (x,y) เป็น c+1 Pieces
Valid Cut: ส่วนที่ตัดออกต้องมี 1 อย่างน้อย 1 และส่วนที่เหลือก็ต้องมี 1 อย่างน้อย 1
Memoization: `@lru_cache` ป้องกันการคำนวณซ้ำ
ตัวอย่าง k=2 บน Matrix 3x3
Matrix:
1 1 0
1 0 1
1 1 1 (Total 7 ones)
Valid Cuts:
Vertical: After Col 0 (Left: 3 ones, Right: 4 ones) ✓
After Col 1 (Left: 5 ones, Right: 2 ones) ✓
Horizontal: After Row 0 (Top: 2 ones, Bottom: 5 ones) ✓
After Row 1 (Top: 4 ones, Bottom: 3 ones) ✓
Total: 4 Ways
Complexity
- Time: O(m × n × k × (m+n)) ≈ O(k × m × n × max(m,n))
- Space: O(m × n × k) สำหรับ Memoization
- Optimization: Precompute Valid Cut Positions
Constraints ทั่วไป: m,n ≤ 50, k ≤ 10, Mod 10⁹+7
