腾讯有一道机试题：
大概意思是：
小Q非常富有，拥有非常多的硬币，小Q的拥有的硬币是有规律的，对于所有的非负整数K,小Q恰好> 各有两个数值为2^k，的硬币，所以小Q拥有的硬币是1，1，2，2，4，4……，小Q卖东西需要支付元钱，请问小Q想知道有多少种组合方案。
输入：一个n (1<=n<=10^18),代表要付的钱
输出：表示小Q可以拼凑的方案数目
输入样例：6
输出样例：3
即：4+2，4+1+1，2+2+1+1
暴力解法
容易得知，对于输入N，所需硬币最大值不会超过N，即只需从1～^logN这些硬币拼凑。每种硬币可选0~2个，共三种选法。排列组合共3^logN种。
回溯法：耗费略优于暴力解法
import java.util.Scanner;
public class Main {
private static int n; //支付数
private static int count=0;
private static int[] p=null; //p[i]记录2^i元的硬币用了多少个，取值0~2 //初始化数组大小
private static void init(){
double lo=Math.log(n)/Math.log(2);
int length=(int)lo+1;
p=new int[length];
} //取值并回溯
private static final void solve(int i){
if(i>=p.length) return;
for(int t=0;t<=2;t++){
p[i]=t;
if(isOK()) count++;
else if(isPart()) solve(i+1);
}
p[i]=0;
} //判断是否当前是否等于n
private static boolean isOK(){
int sum=0;
for(int i=0;i<p.length;i++){
sum+=Math.pow(2, i)*p[i];
}
if(sum==n) return true;
else return false;
} //是否进行延伸
private static boolean isPart(){
int sum=0;
for(int i=0;i<p.length;i++){
sum+=Math.pow(2, i)*p[i];
}
if(sum<n) return true;
else return false;
} public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
scanner.close();
double start=System.currentTimeMillis();
init();
solve(0);
System.out.println(count);
System.out.println("use time="+(System.currentTimeMillis()-start));
}
}
动态规划：耗费远小于回溯
使用res[n,i]表示：使用1，1，2，2，4，4，...，2^i，2^i可以组合出n的方案数
可见
res[n,i]=1，当n=0，即所有面值的硬币所取数目都为0
res[n,i]=1，当n=1，即只取一个一元的硬币
res[2,0]=1，即只取两个一元硬币
res[n,0]=0，当n>=3，因为无法只使用1，1组成大于等于3的组合
res[n,i]=sum(res[n-2^i*m,i-1]) n,i取其他，0=<m<=2
import java.util.Scanner;
public class Main {
private static int n; //支付数
private static int count=0;
private static int[][]res=null; //初始化数组
private static void init(){
double lo=Math.log(n)/Math.log(2);
int length=(int)lo+1;
res=new int[n+1][length];
for(int i=0;i<res[0].length;i++){
res[0][i]=1;
res[1][i]=1;
} res[1][0]=1;
res[2][0]=1;
} //动态规划
private static final int solve(){
if(n==0) return 1;
if(n==1) return 1; init();
for(int i=1;i<n+1;i++){
for(int j=1;j<res[0].length;j++){
int sum=0;
for(int m=0;m<3;m++){
int rest=(int) (i-Math.pow(2, j)*m);
if(rest>=0)
{
sum+=res[rest][j-1];
}
}
res[i][j]=sum;
}
}
return res[n][res[0].length-1];
} public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
scanner.close();
double start=System.currentTimeMillis();
int result=solve();
System.out.println(result);
System.out.println("use time="+(System.currentTimeMillis()-start));
}
}
结果分析：
回溯：测试通过，n=10000时，耗费15s
动态规划：测试通过，n=10000时，耗费32ms
第四种方法:一种很有趣的思路
将硬币分为两份：1，2，4，8，16，.....和1，2，4，8，16....
组成两个数值为a,b的两个数字，他们的和是a+b=n;
a在每一份中只可能有一种组合方式（二进制的思想）。
将a和b使用二进制表示，那么对于n=11，有a=101，b=110这种组合，即a=1+0+4=5,b=0+2+4=6。但是，请注意，对于a和b，在相同位取不同值，只有一种组合方法。
如111+100和101+110（即交换中间位）本质上都是同一种组合方法，因此对于该类型可以使用二进制异或进行去重。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set; public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
if(n<=2) {
System.out.println(n);
return;
}
Set<Integer> countset=new HashSet<>();
int stop=n/2;
for(int i=1;i<=stop;i++) {
int result=(i)^(n-i);//异或a和b
countset.add(result);
}
System.out.println(countset.size());
}
}