LCP 22. 黑白方格畫
小扣注意到秋日市集上有一個(gè)創(chuàng)作黑白方格畫的攤位。攤主給每個(gè)顧客提供一個(gè)固定在墻上的白色畫板，畫板不能轉(zhuǎn)動(dòng)。畫板上有 n * n 的網(wǎng)格。繪畫規(guī)則為，小扣可以選擇任意多行以及任意多列的格子涂成黑色（選擇的整行、整列均需涂成黑色），所選行數(shù)、列數(shù)均可為 0。
小扣希望最終的成品上需要有 k 個(gè)黑色格子，請(qǐng)返回小扣共有多少種涂色方案。
注意：兩個(gè)方案中任意一個(gè)相同位置的格子顏色不同，就視為不同的方案。
示例 1：
輸入：n = 2, k = 2
輸出：4
解釋：一共有四種不同的方案：
第一種方案：涂第一列；
第二種方案：涂第二列；
第三種方案：涂第一行；
第四種方案：涂第二行。
示例 2：
輸入：n = 2, k = 1
輸出：0
解釋：不可行，因?yàn)榈谝淮瓮可辽贂?huì)涂?jī)蓚€(gè)黑格。
示例 3：
輸入：n = 2, k = 4
輸出：1
解釋：共有 2*2=4 個(gè)格子，僅有一種涂色方案。
限制：
1 <= n <= 6
0 <= k <= n * n
依次遍歷，判斷對(duì)應(yīng)的行數(shù)跟列數(shù)是否等于k，然后求C(I,N)也就是高中數(shù)學(xué)里面的排列組合的問題，求出即可；
public class Lcp22 {
? ? public static void main(String[] args) {
? ? ? ? System.out.println(paintingPlan(1,0));
? ? ? ? System.out.println(c(1, 2));
? ? }
? ? public static int paintingPlan(int n, int k){
? ? ? ? if(k==0){
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? if(k==n*n){
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? int cnt=0;
? ? ? ? for (int i = 0; i < n; i++) {
? ? ? ? ? ? for (int j = 0; j < n; j++) {
? ? ? ? ? ? ? ? if(i*n+j*n-i*j==k){
? ? ? ? ? ? ? ? ? ? cnt+=c(i,n)*c(j,n);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return cnt;
? ? }
? ? public static int c(int k,int n){
? ? ? ? if(k==0){
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? if(k==n){
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? if(k>n/2){
? ? ? ? ? ? return c(n-k,n);
? ? ? ? }
? ? ? ? int mul=1;
? ? ? ? for (int i = 0; i < k; i++) {
? ? ? ? ? ? mul=mul*(n-i);
? ? ? ? }
? ? ? ? int div=1;
? ? ? ? for (int i = 0; i < k; i++) {
? ? ? ? ? ? div=div*(1+i);
? ? ? ? }
? ? ? ? return mul/div;
? ? }
}
執(zhí)行用時(shí)：0 ms, 在所有?Java?提交中擊敗了100.00%的用戶
內(nèi)存消耗：38.3 MB, 在所有?Java?提交中擊敗了44.64%的用戶
