状压dp

package com.zhang.reflection.面试.算法模版.动态规划;
import java.util.Scanner;
/**
 * 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。
 * 国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
 *
 * 只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
 * 所得的方案数
 * 3 2
 * 16
 */
public class 状压dp {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();
        int limit=1<<n;
        //用long保存数据
        long[][][] dp=new long[n][limit][82];
        /**
         * 最外层循环为行数{
         *      状态种类枚举{
         *           i=0:出事计数为1
         *           i!=0:状态由上一层的状态得出
         *           需要循环遍历上一层的每个状态
         *      }
         * }
         * 最终循环输出最后一行，并且数量为k的种类和
         */
        for(int i=0;i<n;i++){
            for(int st=0;st<(1<<n);st++){
                if(!check1(st,n)){
                    continue;
                }
                //如果为第0行，则需要直接计数为1
                if(i==0){
                    dp[i][st][oneCount(st)]=1;
                }else{
                    //如果不为第0行，则需要使用动态规划计算上一次的不同状态的计数和
                    for(int j=oneCount(st);j<=k;j++){
                        for(int st2=0;st2<(1<<n);st2++){
                            if(!check1(st2,n)||!check2(st,st2,n)){
                                continue;
                            }
                            dp[i][st][j]+=dp[i-1][st2][j-oneCount(st)];
                        }
                    }
                }
            }
        }
        //方法数量可能很多，需要用long来保存结果
        long result=0;
        for(int i=0;i<(1<<n);i++){
            result+=dp[n-1][i][k];
        }
        System.out.println(result);
    }
    //f返回st的二进制表示中1的个数
    private static int oneCount(int st){
        return Integer.bitCount(st);
    }
    //判断单行st状态是否合法
    private static boolean check1(int st,int n){
        for(int i=0;i+1<n;i++){
            if((st&(1<<i))!=0&&(st&(1<<(i+1)))!=0){
                return false;
            }
        }
        return true;
    }
    //判断当前行状态st1和上一行状态st2是否合法
    private static  boolean check2(int st1,int st2,int n){
        for(int i=0;i<n;i++){
            if((st1&(1<<i))!=0){
                if((st2&(1<<i))!=0){
                    return false;
                }else if(i-1>=0&&(st2&(1<<(i-1)))!=0){
                    return false;
                }else if(i+1<n&&(st2&(1<<(i+1)))!=0){
                    return false;
                }
            }
        }
        return true;
    }
}