LCP 22. 黑白方格画 （JavaScript，数学组合解法）

LCP 22. 黑白方格画 小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 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

解题思路

对大佬的思路加以补充：判断a行b列需要进行两个for循环判断

题解

大佬的Java解法改成JavaScript解法

/** * @param {number} n * @param {number} k * @return {number} */ var paintingPlan = function (n, k) { if (k == n * n) return 1 let res = 0 let C = (n, m) => { let res = 1 for (let i = n; i > m; i--) res *= i //m之后的与下面的m的阶乘抵消，需要到此处即可 for (let i = n - m; i > 0; i--) res /= i return res } for (let i = 0; i <= n; i++) { for (let j = 0; j <= n; j++) { //判断出i行j列 let sum = i * n + j * n - i * j if (sum == k) { //符合总数要求，开始计算该i行j列下的组合数 let x = C(n, i) let y = C(n, j) res += x * y } } } return res };

部分内容来自： 作者：qi-shi-wo-shi-yi-ge-yan-yuan 链接：https://leetcode-cn.com/problems/ccw6C7/solution/lcp-22-hei-bai-fang-ge-hua-by-qi-shi-wo-shi-yi-ge-/