#每日一題 力扣第22題 黑白格子畫

今天同樣是一道雙變量的題目，通過行數和列樹來控制總的黑色格子數。

小扣注意到秋日市集上有一個創作黑白方格畫的攤位。攤主給每個顧客提供一個固定在牆上的白色畫闆，畫闆不能轉動。畫闆上有 n * n 的網格。繪畫規則為，小扣可以選擇任意多行以及任意多列的格子塗成黑色（選擇的整行、整列均需塗成黑色），所選行數、列數均可為 0。

小扣希望最終的成品上需要有 k 個黑色格子，請傳回小扣共有多少種塗色方案。

注意：兩個方案中任意一個相同位置的格子顔色不同，就視為不同的方案。

示例 1：

輸入：n = 2, k = 2

輸出：4

解釋：一共有四種不同的方案：

第一種方案：塗第一列；

第二種方案：塗第二列；

第三種方案：塗第一行；

第四種方案：塗第二行。

因為是兩個變量，我們采用“定一變一”的方法來設定周遊，先定行數p，行數p可以塗上n*p個有效黑色塊，列數q可以塗上（n-p)*q個有效黑色塊。然後确定了p和q之後，計算組合數C(n,p)*C(n,q)

class Solution {
public:
     //計算組合數C(n,x)
    int fun(int x,int n){
        int a=1,b=1;
        for(int i=n;i>(n-x);i--)
            a*=i;
        for(int i=1;i<=x;i++)
            b*=i;
        return a/b;
    }
    
    int paintingPlan(int n, int k) {
       //根據題目，當整個畫布都被塗滿時，隻有一種方案
        if(k==n*n)
            return 1;
        int temp=0;
        //先定行數
        for(int p=0;p<=n;p++){
            if(p*n>k)
                break;
        //再定列數
            for(int q=0;q<=n;q++){
                if(p*n+q*(n-p)==k){
                   //将此方案數記錄下來
                    temp+=(fun(p,n)*fun(q,n));
                    break;
                }
            }
        }  
        return temp;         
    }
};
           

此方案的時間複雜度為O(n^2)，那能不能想辦法降低時間複雜度呢，我們發現根據p可以直接定出q，q=(k-p*n)/（n-p）,這樣就可以降為O(n)。

代碼如下：

class Solution {
public:
    int fun(int x,int n){
        int a=1,b=1;
        for(int i=n;i>(n-x);i--)
            a*=i;
        for(int i=1;i<=x;i++)
            b*=i;
        return a/b;
    }
    int paintingPlan(int n, int k) {
        if(k==n*n)
            return 1;
        int temp=0;
        for(int p=0,q=0;p<=n;p++){
            if(p*n>k)
                break;
            //直接根據行數p計算出對應的列數q
            if((k-p*n)%(n-p)==0){
                q=(k-p*n)/(n-p);
                if(q<=n)
                    temp+=(fun(p,n)*fun(q,n));
            }
        }  
        return temp;         
    }
};