题解 2112: 决战拼接

参考代码:

import java.util.Scanner;
public class T2112 {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();//部队数
		int num[]=new int[n];
		for (int i = 0; i < num.length; i++) {
			num[i]=scanner.nextInt();
		}
		int m=scanner.nextInt();//战斗力
		int dp[]=new int[m+1];//每个战斗力的最优解合成次数
		for (int i = 0; i < dp.length; i++) {
			dp[i]=Integer.MAX_VALUE;//设置默认值整型最大数
		}
		for (int i = 0; i < n; i++) {
			if (num[i]<=m) {
				dp[num[i]]=1;//每个部队战斗力自身最优解决方案是1
			}
		}
		for (int i = 1; i <=m; i++) {
			for (int j = 0; j < n; j++) {
				if (i-num[j]>=0&&dp[i-num[j]]!=Integer.MAX_VALUE) { //为默认值Integer.MAX_VALUE则没有合成次数
					dp[i]=Math.min(dp[i], dp[i-num[j]]+1);//比较合成次数
				}
			}
		}
		if (dp[m]==Integer.MAX_VALUE) {//没有合成次数
			System.out.println(-1);
		}
		else {
			System.out.println(dp[m]);
		}
	}
}