題目
标題：包子湊數
小明幾乎每天早晨都會在一家包子鋪吃早餐。他發現這家包子鋪有N種蒸籠，其中第i種蒸籠恰好能放Ai個包子。每種蒸籠都有非常多籠，可以認為是無限籠。
每當有顧客想買X個包子，賣包子的大叔就會迅速選出若幹籠包子來，使得這若幹籠中恰好一共有X個包子。比如一共有3種蒸籠，分别能放3、4和5個包子。當顧客想買11個包子時，大叔就會選2籠3個的再加1籠5個的(也可能選出1籠3個的再加2籠4個的)。
當然有時包子大叔無論如何也湊不出顧客想買的數量。比如一共有3種蒸籠，分别能放4、5和6個包子。而顧客想買7個包子時，大叔就湊不出來了。
小明想知道一共有多少種數目是包子大叔湊不出來的。
輸入
第一行包含一個整數N。(1 <= N <= 100)
以下N行每行包含一個整數Ai。(1 <= Ai <= 100)
輸出
一個整數代表答案。如果湊不出的數目有無限多個，輸出INF。
例如，
輸入：
2
4
5
程式應該輸出：
6
再例如，
輸入：
2
4
6
程式應該輸出：
INF
樣例解釋：
對于樣例1，湊不出的數目包括：1, 2, 3, 6, 7, 11。
對于樣例2，所有奇數都湊不出來，是以有無限多個。
資源約定：
峰值記憶體消耗(含虛拟機) < 256M
CPU消耗 < 1000ms
請嚴格按要求輸出，不要畫蛇添足地列印類似：“請您輸入...” 的多餘内容。
所有代碼放在同一個源檔案中，調試通過後，拷貝送出該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是：Main，否則按無效代碼處理。
送出程式時，注意選擇所期望的語言類型和編譯器類型。
思路：
首先如果兩籠包子分别是2和4，兩個都是偶數，那麼就直接print輸出INF，因為他們永遠無法湊出奇數；如果一個是3一個是4或者兩個都是奇數那麼就可以開始下一步計算。
這裡我們使用動态規劃的思路去解決
我們建立一個狀态表，去記錄每個下标是否可以湊包子，我們用其下标當做顧客的要求。比如他要3個包子，我們可以湊出，就status[3] = true
我們根據給出的每籠包子數把狀态表填滿，在求出其false的個數就是無法滿足需求的個數。
怎麼填呢？我們先設定一個周遊包子種數的循環，初始化status[0] = true和status[input[0]] = true,假如第一種籠包子數是2 ，那麼我們就可以配出0個和2個包子，這時候我們周遊到status[2]的時候，發現他是true，我們就可以在他基礎上加上2，status[2+2]=true ，加2到狀态表盡頭後，我們就去處理下一種籠數，碰到status[2]的時候發現他是true，那麼就可以加上目前包子種數組成一個新的組合 比如2+3等于5
下面看代碼
public class Main {
//判斷ab之間是否互質 否則輸出INF
static public int gcd(int a, int b){
if (b == 0) return a;
return gcd(b,a%b);
}
public static void main(String[] args) {
// write your code her
//我這裡沒有擷取輸入内容，直接用數組去模拟，你可以通過nextInt拿到數組。
int [] input = {4,7};
getCount(input);
}
public static int getCount(int[] input)
{
int g = input[0];
boolean[] status = new boolean[10000];
for (int i = 1; i < input.length; i++) {
g = gcd(g,input[i]);
}
//你也可以這樣 if (input[1]%2 != 0 || input[0]%2 != 0.....)，不過要判斷數組所有裡面的元素
if (g!=1){
System.out.println("INF");
}else
{
//互質
//開始計算
//我們要對這頭一個數和該數的下标做一下處理，友善後面計算
status[0] = true;
status[input[0]] = true;
for (int i = 0; i < input.length; i++) {
for (int j = 0;j < status.length-input[i]; j++) {
if (input[i]+j
{
if (status[j]==true)
status[input[i]+j] = true;
}
}
}
int count = 0;
for (int i = 0; i < status.length; i++) {
if (status[i] == false){
count++;
}
}
System.out.println(count);
}
return 0;
}
}