import java.util.BitSet;
public class BTGame{
private static final int MAX = 500;
private static BitSet isSuit =new BitSet(offset(MAX+1)), isSolved =new BitSet(offset(MAX+1));
static{
for(int k=0;k<=MAX;k++){isSuit.set(offset(k)); isSolved.set(offset(k));}
}
private static int offset(int n){ //表示第n个的起始位置
return n*(n-1)*(n-2)/6 + n;
}
public static boolean isSuit(int n,int k){
if(k<0||k>n*(n-1)/2) return false;
int off =offset(n);
if(isSolved.get(off+k)) return isSuit.get(off+k);
for(int i =1;i
if(isSuit(n -i,k -i*(n-i) ) ){
isSolved.set(off +k);
isSuit.set(off +k);
return true;
}
isSolved.set(off +k);
return false;
}
public static void test(int n,int k){
System.out.println(isSuit(n,k)?"YES":"NO");
}
public static void main(String[] args){
test(2,0);
test(2,1);
test(3,1);
test(3,2);
test(5,4);
test(5,5);
}
}

递规算法