文章目錄
- 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阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/89530.html
標籤：其他
上一篇：MONGODB怎么修改一些變化值的資料（用函式獲取到的變化數值）
下一篇：小白求帶