背包問題具備的特征：給定一個(gè)target灶似，target可以是數(shù)字也可以是字符串列林，再給定一個(gè)數(shù)組nums，nums中裝的可能是數(shù)字酪惭，也可能是字符串希痴，問：能否使用nums中的元素做各種排列組合得到target。
組合問題核心公式：dp[i] += dp[i - num]
Tips:
- 如果是完全背包春感，即數(shù)組中的元素可重復(fù)使用砌创，
nums放在外循環(huán)，target在內(nèi)循環(huán)鲫懒。且內(nèi)循環(huán)正序嫩实。 - 如果是0-1背包，即數(shù)組中的元素不可重復(fù)使用窥岩，
nums放在外循環(huán)甲献，target在內(nèi)循環(huán)，且內(nèi)循環(huán)倒序颂翼； - 如果組合問題（完全背包問題）需考慮元素之間的順序晃洒，需將
target放在外循環(huán)，將nums放在內(nèi)循環(huán)朦乏，（如T377零錢兌換球及、T70爬樓梯、T139單詞拆分）呻疹。
ps：不涉及順序的完全背包問題吃引，nums和target在內(nèi)外循環(huán)都可以，但建議nums外循環(huán)，target內(nèi)循環(huán)际歼。
1.目標(biāo)和 （494-中）
題目描述：給定一個(gè)非負(fù)整數(shù)數(shù)組a1, a2, ..., an和一個(gè)目標(biāo)數(shù)S』谭現(xiàn)在你有兩個(gè)符號(hào)+ 和-。對(duì)于數(shù)組中的任意一個(gè)整數(shù)鹅心，你都可以從+ 或 -中選擇一個(gè)符號(hào)添加在前面吕粗。
返回可以使最終數(shù)組和為目標(biāo)數(shù) S 的所有添加符號(hào)的方法數(shù)。
示例：
輸入：nums: [1, 1, 1, 1, 1], S: 3
輸出：5
解釋：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5種方法讓最終目標(biāo)和為3旭愧。
思路：
法1：dfs：使用遞歸颅筋，以每個(gè)位置作為起始位置，遞歸的終止條件是start == nums.length输枯，檢查是否為目標(biāo)值议泵，對(duì)于每一個(gè)起始位置start，都有兩種狀態(tài)（正或負(fù)）桃熄。
法2：動(dòng)態(tài)規(guī)劃：元素只能用一次先口，01背包問題。dp[i]表示前i個(gè)數(shù)能達(dá)到的值瞳收，對(duì)于整數(shù)i有兩種狀態(tài)+i 和 -i碉京，即整個(gè)數(shù)組和劃分為P(使用正號(hào))和N(使用負(fù)號(hào))兩個(gè)部分。我們要轉(zhuǎn)化為背包問題螟深，關(guān)鍵是：在集合nums中找到一個(gè)和等于(S + sum(nums))/2子集谐宙，就證明存在解。
推導(dǎo)：
P - N = target ....1
P + N = sum(nums) ....2
帶入消除N得：P = (sum(nums) + target) / 2
代碼1：dfs
public int findTargetSumWays(int[] nums, int S) {
return findTargetSumWays(nums, 0, S);
}
public int findTargetSumWays(int[] nums, int start, int S) {
if (start == nums.length) {
// 終止條件
return S == 0 ? 1 : 0;
}
// 對(duì)于每個(gè)起始位置界弧，遞歸的進(jìn)行求解兩種狀態(tài)組合數(shù)
return findTargetSumWays(nums, start + 1, S - nums[start]) +
findTargetSumWays(nums, start + 1, S + nums[start]);
}
代碼2：動(dòng)態(tài)規(guī)劃
public int findTargetSumWays(int[] nums, int S) {
int sum = sumArray(nums);
// 待尋找目標(biāo)值
int W = (S + sum) / 2;
// 邊界：一定不能達(dá)到目標(biāo)的情況凡蜻！
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int[] dp = new int[W + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = W; i >= num; --i) {
dp[i] += dp[i - num];
}
}
return dp[W];
}
private int sumArray(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
2.零錢兌換II（518-中）
題目描述：給定不同面額的硬幣coins 和一個(gè)總金額 amount。求解可以湊成總金額的硬幣組合總數(shù)垢箕。注：每種硬幣的數(shù)量是無限的划栓。
示例：
輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
輸入: amount = 3, coins = [2]
輸出: 0
解釋: 只用面額2的硬幣不能湊成總金額3。
思路：完全背包問題舰讹，直接動(dòng)態(tài)規(guī)劃茅姜。
dp[i]：達(dá)到金額i的組合數(shù)。- 狀態(tài)轉(zhuǎn)移方程：
dp[i] += dp[i - coin]; - 邊界條件月匣，當(dāng)
amount = 0，可達(dá)成的目標(biāo)數(shù)（方案）為1奋姿，即一個(gè)也不選锄开， 所以dp[0] = 1.
代碼：動(dòng)態(tài)規(guī)劃
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
// 目標(biāo)值為0，有一種方案：什么都不選
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; ++i) {
//dp[i]依賴 dp[i -coin] 要先算出來称诗，即遞增for循環(huán)
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
3.組合總和IV（377-中）
題目描述：給定一個(gè)由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組（但可以復(fù)用多次）萍悴，找出和為給定目標(biāo)正整數(shù)的組合的個(gè)數(shù)。請(qǐng)注意！順序不同的序列被視作不同的組合癣诱。
- 進(jìn)階： 如果給定的數(shù)組中含有負(fù)數(shù)會(huì)怎么樣计维？ 問題會(huì)產(chǎn)生什么變化？ 我們需要在題目中添加什么限制來允許負(fù)數(shù)的出現(xiàn)撕予？
示例：
nums = [1, 2, 3]
target = 4
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
因此輸出為 7鲫惶。
思路：動(dòng)態(tài)規(guī)劃：本題的完全背包涉及順序，與518.零錢兌換II不同點(diǎn)实抡。其中欠母，dp[i]代表和等于i的組合的個(gè)數(shù)。背包問題空間壓縮：dp[i]依賴 dp[i - nums[j]] 要先算出來吆寨，即內(nèi)層遞增for循環(huán)赏淌。
代碼：動(dòng)態(tài)規(guī)劃
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 這個(gè)值被其它狀態(tài)參考，設(shè)置為 1 是合理的
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
進(jìn)階問題：參考這里
1啄清、如果給定的數(shù)組中含有負(fù)數(shù)會(huì)怎么樣六水？問題會(huì)產(chǎn)生什么變化？
如果有負(fù)數(shù)辣卒，相當(dāng)于給定數(shù)組中的元素有了更多的組合掷贾，特別是出現(xiàn)了一對(duì)相反數(shù)的時(shí)候，例如題目中的示例 [-4, 1, 2, 3, 4]添寺，target = 4 的時(shí)候胯盯，-4 和 4 可以無限次地、成對(duì)添加到題目中的示例中计露，成為新的組合博脑，那么這道問題就沒有什么意義了。
仔細(xì)思考票罐，負(fù)數(shù)我只要不選它就行叉趣。但由于本題的問法是“組合”，因此我們要保證有負(fù)數(shù)參與進(jìn)來该押，不能夠與已有的正數(shù)的組合之和為 0 即可疗杉。
2、我們需要在題目中添加什么限制來允許負(fù)數(shù)的出現(xiàn)蚕礼？
- 如果有負(fù)數(shù)參與進(jìn)來烟具，不能夠與已有的正數(shù)的組合之和為 0 ；
- 或者限制負(fù)數(shù)的使用次數(shù)奠蹬，設(shè)計(jì)成類似 0-1 背包問題的樣子朝聋。
4.爬樓梯（70-易）
題目描述：假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂囤躁。每次你可以爬 1 或 2 個(gè)臺(tái)階冀痕。你有多少種不同的方法可以爬到樓頂呢荔睹？
示例：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. 1 階 + 1 階
2. 2 階
思路：動(dòng)態(tài)規(guī)劃：完全背包解法言蛇。其中：dp[i]表示到第n階有多少種不同方法僻他。
代碼：動(dòng)態(tài)規(guī)劃
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 1; j <= n; ++j) {
for (int i = 1; i <= 2; ++i) {
if (i <= j) {
dp[j] += dp[j - i];
}
}
}
return dp[n];
}
