文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

小扣注意到秋日市集上有一個創作黑白方格畫的攤位。
攤主給每個顧客提供一個固定在墻上的白色畫板，畫板不能轉動。
畫板上有 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

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/ccw6C7
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution { public:int paintingPlan(int n, int k) {int x, y, ans = 0;if(n*n == k) return 1;//肯定只有一種方案for(x = 0; x <= n; ++x) {for(y = 0; y <= n; ++y){if((x+y)*n-x*y == k){ans += C(n,x)*C(n,y);//兩個方向的組合數相乘}}}return ans;}int C(int n, int x){int up = 1, t = x, down = 1;while(t--){up *= n--;down *= x--;}return up/down;} };

0 ms 5.9 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode LCP 22. 黑白方格画的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。