小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。
画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。
小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。
注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。
示例 1：
输入：n = 2, k = 2
输出：4
解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。
示例 2：
输入：n = 2, k = 1
输出：0
解释：不可行，因为第一次涂色至少会涂两个黑格。
示例 3：
输入：n = 2, k = 4
输出：1
解释：共有 2*2=4 个格子，仅有一种涂色方案。
限制：
1 <= n <= 6
0 <= k <= n * n
自我解答
这题我想了很久，最终依靠提示，思考出了动态规划的解法。
每次涂色都可以行或列，假如 涂了 1 行，那么接下来，涂列新增的黑格子数都是 n - 1。
假设 xsize, ysize 分别是 涂行、列的 新增黑格子数，初始都是 n,
设 f(k, xsize, ysize) 为 黑格子数是 k 的方案数
会存在以下递推式：
f(k, xsize, ysize) = f(k-xsize, xsize, ysize-1) + f(k-ysize, xsize-1, ysize)
由此，可以设计一个递归算法，当 k == 0 时，我们就得到了一个方案了：
此时可以通过 n - ysize, n - xsize 获得这个方案的 行列数
通过计算行列的组合数 获得这个行列组合的所有方案数
需要注意2点：
1、这个算法会重复递归行列相同的方案，因此需要对此标记去重
2、当 k == n*n 时，这个递归算法就不适用了,
因为，(n行，0列)， (0行，n列)，(n-1行，n列) 都算是一个方案
除了这个情况，其他的 (x行，y列) 都是唯一的
class Solution:
def paintingPlan(self, n: int, k: int) -> int:
if k in (0, n * n):
return 1
self.n = n
self.history = {}
return self.paint(k, n, n)
def paint(self, k: int, xsize: int, ysize: int) -> int:
if k == 0:
x = self.n - ysize
y = self.n - xsize
if (x, y) in self.history:
return 0
# num = math.comb(self.n, x) * math.comb(self.n, y) # python3.8
num = self.comb(self.n, x) * self.comb(self.n, y)
self.history[(x, y)] = num
return num
num = 0
if xsize <= k:
num += self.paint(k - xsize, xsize, ysize - 1)
if ysize <= k:
num += self.paint(k - ysize, xsize - 1, ysize)
return num
@staticmethod
def comb(n, m):
if m in (0, n):
return 1
_n, _m, _n_m = n, m, n - m
for i in range(1, n):
_n *= i
for i in range(1, m):
_m *= i
for i in range(1, n - m):
_n_m *= i
return _n // (_m * _n_m)
题解
题解中的解法类似，更加简洁、巧妙，可以称作是上面的 非递归版本。
不模拟涂的过程，直接计算考虑所有的行列组合数，因为通过 (x行， y列)可以直接计算出黑格子数。
因此，找出可行的行列数，再以此计算 组合数就行
class Solution2:
def paintingPlan(self, n: int, k: int) -> int:
if k in (0, n * n):
return 1
res = 0
for x in range(n):
for y in range(n):
if n * (x + y) - (x * y) == k:
res += self.comb(n, x) * self.comb(n, y)
return res
@staticmethod
def comb(n, m):
if m in (0, n):
return 1
_n, _m, _n_m = n, m, n - m
for i in range(1, n):
_n *= i
for i in range(1, m):
_m *= i
for i in range(1, n - m):
_n_m *= i
return _n // (_m * _n_m)
总结
这题挺难的，所有人的通过率是 31%。
需要去找规律
1、分析归纳出通过x行, y列 这样来确定”一类“方案
2、计算x行, y列的组合数，为此我还需要去复习排列组合
排列：从 n 个数中选出 m 个数，不同的选出顺序是不同的方案， n!/(n-m)!
组合：从 n 个数中选出 m 个数，不考虑选出顺序，n!/(m!(n-m)!)
3、还要分析出 k == n*n 这样的特殊情况，没有意识到的话，很可能以此去否定整个方案