數組的最小不可組成和問題
作者：Grey
原文地址：數組的最小不可組成和問題
題目說明
鏈接：//www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
來源：牛客網給定一個全是正數的數組arr，定義一下arr的最小不可組成和的概念：
1，arr的所有非空子集中，把每個子集內的所有元素加起來會出現很多的值，其中最小的記為min，最大的記為max；
2，在區間[min,max]上，如果有一些正數不可以被arr某一個子集相加得到，那麼這些正數中最小的那個，就是arr的最小不可組成和；
3，在區間[min,max]上，如果所有的數都可以被arr的某一個子集相加得到，那麼max+1是arr的最小不可組成和；
舉例： arr = {3,2,5}
arr的min為2，max為10，
在區間[2,10]上，4是不能被任何一個子集相加得到的值中最小的，所以4是arr的最小不可組成和；
arr = {3,2,4}
arr的min為2，max為9，
在區間[2,9]上，8是不能被任何一個子集相加得到的值中最小的，所以8是arr的最小不可組成和；
arr = {3,1,2} arr的min為1，max為6，
在區間[2,6]上，任何數都可以被某一個子集相加得到，所以7是arr的最小不可組成和；
請寫函數返回arr的最小不可組成和。
思路
首先我們設置兩個變量，max和min用於記錄數組累加得到的最大值，和當數組不為空累加得到的最小值。那麼在數組非空狀態下，累加和一定在[min, max]區間內。我們設置
boolean[][] dp = new boolean[arr.length][max + 1];
其中dp[i][j]表示[0....i]範圍內的元素任意累加，能否組成j這個累加和
顯然有
// 0元素可以組成arr[0]這個累加和
dp[0][arr[0]] = true;
for (int i = 0; i < dp.length; i++) {
// 0..i上一個元素都不用，可以組成0這個累加和
dp[i][0] = true;
}
這樣我們得到dp這個數組第一行和第一列的情況。
然後我們可以推導普遍位置
dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
其含義為：
[0...i]範圍內，任意選擇，能否組成j這個累加和，其實包括了兩種情況：
情況1：[0...i-1]範圍內，任意選擇，能否組成j這個累加和，如果可以，說明dp[i][j]=true
情況2：[0...i-1]範圍內，任意選擇，能否組成j-arr[i]這個累加和（注意不能越界），如果可以，說明dp[i][j] = true
所以，普遍位置的求法如下
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < max + 1; j++) {
dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
}
}
經過上述處理，dp已全部填好，接下來就是判斷dp中第一個為false的位置，即為答案
for (int i = min; i <= max; i++) {
if (!dp[arr.length - 1][i]) {
return i;
}
}
如果上述過程沒有找到，則返回max+1，完整代碼如下
public static int getFirstUnFormedNum(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
max += arr[i];
min = Math.min(min, arr[i]);
}
// 可以到的範圍是[min,max]
// dp[i][j] 0....i能否組成j
boolean[][] dp = new boolean[arr.length][max + 1];
// 第0行 除了下述位置，其他位置都是false
dp[0][arr[0]] = true;
for (int i = 0; i < dp.length; i++) {
// 0..i上一個元素都不用，可以組成0這個累加和
dp[i][0] = true;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < max + 1; j++) {
dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
}
}
for (int i = min; i <= max; i++) {
if (!dp[arr.length - 1][i]) {
return i;
}
}
return max + 1;
}
