java 动态规划方法

解题思路:

注意事项:它虽然可以过，但是过不了最大的样例，并不能算完全正确

参考代码:

import java.math.BigInteger;
import java.security.PKCS12Attribute;
import java.util.DoubleSummaryStatistics;
import java.util.Scanner;

public  class  Main {
	//这里是写了一个排列组合，在N1个数中取N2个（不能重复），变相满足了题目要求的大小排序要求
	public static void main(String[] args) {
		long [][]b1 = new long[500][500];
		Scanner scanner = new Scanner(System.in);
		//k代表2^k,w表示最大的二进制位数
		int k = scanner.nextInt();
		int w = scanner.nextInt();
		int sum = (int)Math.pow(2.0, k)-1;//求范围，也就是可以取得数[sum][num]
		int num = w/k;
		int flag = w%k;
		b1[0][0]=1;
		for(int i=1;i<=sum;i++)
		{
			for(int j=0;j<=sum;j++)
			{
			if(j!=0){	
				//由排列组合公式推出来
				b1[i][j] =b1[i-1][j]+b1[i-1][j-1];
			}else {
				b1[i][j] = b1[i-1][j];
			}
			}
		}
		long B2 =0;
		for(int i=2;i<=num;i++)
		{
			B2 = b1[sum][i]+B2;
		}
		for(int i = 1;i<=flag;i++)
		{
			B2 = b1[sum-i][num]+ B2;
		}
		System.out.println(B2);
	
}
	}