小扣注意到秋日市集上有一個創作黑白方格畫的攤位。
攤主給每個顧客提供一個固定在牆上的白色畫板,畫板不能轉動。
畫板上有 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
著作權歸領釦網路所有。商業轉載請聯絡官方授權,非商業轉載請註明出處。
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阿明),一起加油、一起學習進步!