資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：計算將矩陣分割成k塊的方法數
假設我們有一個二進位制矩陣和另一個值k。你想將矩陣分成k塊，使得每塊至少包含一個1。但是切割有一些規則需要遵循：1. 選擇方向：垂直或水平 2. 選擇矩陣中的一個索引進行切割，分成兩部分。 3. 如果垂直切割，則不能再切割左部分，只能繼續切割右部分。 4. 如果水平切割，則不能再切割上部分，只能繼續切割下部分。所以我們必須找到劃分矩陣的不同方法的數量。如果答案非常大，則返回結果模 (10^9 + 7)。
所以，如果輸入像這樣：
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
k = 2，則輸出將為4，因為我們可以垂直切割兩次，水平切割兩次。
為了解決這個問題，我們將遵循以下步驟：
- p := 10^9 + 7
- m := 矩陣的行數，n := 矩陣的列數
- counts := 一個空對映
- 對於 i 從 m - 1 到 0：
- 對於 j 從 n - 1 到 0：
- counts[i, j] := counts[i + 1, j] + counts[(i, j + 1) ] - counts[(i + 1, j + 1) ] + matrix[i, j]
- 對於 j 從 n - 1 到 0：
- 定義一個函式 f()。它將接收 x, y, c
- count := counts[x, y]
- 如果 c 等於 0，則
- 如果 count > 0 則返回 1，否則返回 0
- ans := 0
- 對於 i 從 x + 1 到 m - 1：
- 如果 0 < counts[(i, y)] < count，則
- ans := ans + f(i, y, c - 1)
- 如果 0 < counts[(i, y)] < count，則
- 對於 j 從 y + 1 到 n - 1：
- 如果 0 < counts[(x, j)] < count，則
- ans := ans + f(x, j, c - 1)
- 如果 0 < counts[(x, j)] < count，則
- 返回 ans mod p
- 從主方法呼叫並返回 f(0, 0, k - 1)
讓我們看看下面的實現，以便更好地理解：
示例
from collections import defaultdict class Solution: def solve(self, matrix, k): p = 10 ** 9 + 7 m, n = len(matrix), len(matrix[0]) counts = defaultdict(int) for i in range(m)[::-1]: for j in range(n)[::-1]: counts[(i, j)] = (counts[(i + 1, j)] + counts[(i, j + 1)] - counts[(i + 1, j + 1)] + matrix[i][j]) def f(x, y, c): count = counts[(x, y)] if c == 0: return 1 if count > 0 else 0 ans = 0 for i in range(x + 1, m): if 0 < counts[(i, y)] < count: ans += f(i, y, c - 1) for j in range(y + 1, n): if 0 < counts[(x, j)] < count: ans += f(x, j, c - 1) return ans % p return f(0, 0, k - 1) ob = Solution() matrix = [ [1, 1, 0], [1, 0, 1], [1, 1, 1], ] k = 2 print(ob.solve(matrix, k))
輸入
[ [1, 1, 0], [1, 0, 1], [1, 1, 1] ], 2
輸出
4
更新於：2020年12月3日
163 次瀏覽
廣告