LCP 22. 黑白方格画

Posted on | In
Words count in article: 416 | Reading time ≈ 1

题目

小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色（选择的整行、整列均需涂成黑色），所选行数、列数均可为 0。

小扣希望最终的成品上需要有k 个黑色格子，请返回小扣共有多少种涂色方案。

注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。

示例 1:

1
2
3
4
5
6
7
8
9
输入：n = 2, k = 2

输出：4

解释：一共有四种不同的方案：
第一种方案：涂第一列；
第二种方案：涂第二列；
第三种方案：涂第一行；
第四种方案：涂第二行。

示例2：

1
2
3
4
5
输入：n = 2, k = 1

输出：0

解释：不可行，因为第一次涂色至少会涂两个黑格。

示例3：

1
2
3
4
5
输入：n = 2, k = 4

输出：1

解释：共有 2*2=4 个格子，仅有一种涂色方案。

提示：

  • 1 <= n <= 6
  • 0 <= k <= n * n

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int paintingPlan(int n, int k) {
        if (n * n == k) {
            return 1;
        }
        int result = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0; j < n;j++) {
                if (i * n + j * n - i * j == k) {
                    result += fractial(n, i) * fractial(n, j);
                }
            }
        }
        return result;
    }

    private int fractial(int n, int c) {
        int sum = 1;
        for (int i = n;i > n - c;i--) {
            sum *= i;
        }

        for (int i = 1;i <= c;i++) {
            sum /= i;
        }
        return sum;
    }
0%