算法|8.從暴力遞歸到動態(tài)規(guī)劃1

目前感覺，背包問題和貨幣數(shù)組問題本質相同，貨幣的與dp相關的三種代碼寫完了，快復習不完了，背包暫時先不寫了，回頭再寫，補充，再總結，結合那個C++大神的文章再弄。

背包類問題

目前來講，我接觸到的背包問題有四種分別是01背包、完全背包、多重背包、以及部分背包。背包問題都屬于NP問題（非直接求解問題），前三種一般使用動態(tài)規(guī)劃進行求解，后一種一般使用貪心求解。

01背包

題意：給定兩個長度都為N的數(shù)組weights和values，weights[i]和values[i]分別代表 i號物品的重量和價值。給定一個正數(shù)bag，表示一個載重bag的袋子，裝的物品不能超過這個重量。返回能裝下的最大價值

解題思路：

• 先寫出遞歸版本，然后對照著改dp。
• 要與不要。結果越大越好，是正向決策，同時使用的累加。
• 參數(shù)設置：重量數(shù)組w、價值數(shù)組v、當前決策到的坐標index、背包剩余的空間rest
• 可變參數(shù)為index和rest，所以dp表是一張二維表。

核心代碼：

遞歸代碼：

public static int maxValue(int[] w, int[] v, int bag) {if(w==null||v==null||w.length!=v.length||w.length==0){return 0;}return process(w,v,0,bag);
}public static int process(int[] w, int[] v, int index, int rest) {if(rest<0){return -1;}if(index==w.length){return 0;}int p1=process(w,v,index+1,rest);int p2=0;int next=process(w,v,index+1,rest-w[index]);if(next!=-1){p2=v[index]+next;}return Math.max(p1,p2);
}

dp代碼：

public static int dp(int[] w, int[] v, int bag) {if (w == null || v == null || w.length != v.length || w.length == 0) {return 0;}int N=w.length;int[][] dp=new int[N+1][bag+1];for (int index = N-1; index >=0 ; index--) {for (int rest = 0; rest <=bag ; rest++) {int p1=dp[index+1][rest];int p2=0;int next=rest-w[index]<0?-1:dp[index+1][rest-w[index]];if(next!=-1){p2=v[index]+next;}dp[index][rest]=Math.max(p1,p2);}}return dp[0][bag];
}

測試代碼：

public static void main(String[] args) {int[] weights = { 3, 2, 4, 7, 3, 1, 7 };int[] values = { 5, 6, 3, 19, 12, 4, 2 };int bag = 15;System.out.println(maxValue(weights, values, bag));System.out.println(dp(weights, values, bag));
}

測試結果：

完全背包

題意：有 N種物品和一個容量為C的背包，每種物品都有無限件。第 i件物品的體積是 v[i]，價值是w[i] .求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。

解題思路：

核心代碼：

測試代碼：

測試結果：

多重背包

題意：有 N種物品和一個容量為C的背包，數(shù)量為s[i]。第 i件物品的體積是 v[i]，價值是w[i] .求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

解題思路：

核心代碼：

測試代碼：

測試結果：

貨幣類問題

組成aim的方法數(shù)（每張認為是一種）

題意：arr是貨幣數(shù)組，其中的值都是正數(shù)。再給定一個正數(shù)aim。
每個值都認為是一張貨幣，即便是值相同的貨幣也認為每一張都是不同的，
返回組成aim的方法數(shù)。例如：arr = {1,1,1}，aim = 2。
第0個和第1個能組成2，第1個和第2個能組成2，第0個和第2個能組成2
一共就3種方法，所以返回3

解題思路：

• 這一題其實和01背包問題很像，只是這個是要求正好組成aim，01背包則是不超過的方法數(shù)
• 所以這里我們只需要在aim=0時返回1，總金額超過了|根本就組不成（錢不夠）就返回0
• 注意：改寫過程中三目操作符建議加上括號（血淋淋的教訓…）// dp[index][rest] = dp[index + 1][rest] + (rest - arr[index]) < 0 ? 0 : dp[index + 1][rest - arr[index]];

核心代碼：

暴力遞歸：

public static int coinWays(int[] arr, int aim) {return process(arr, 0, aim);
}public static int process(int[] arr, int index, int rest) {if (rest < 0) {return 0;}if (index == arr.length) {return rest == 0 ? 1 : 0;}return process(arr, index + 1, rest - arr[index])+ process(arr, index + 1, rest);
}

dp:

    public static int dp(int[] arr, int aim) {if (aim == 0) {return 1;}int N = arr.length;int[][] dp = new int[N + 1][aim + 1];dp[N][0] = 1;for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {
//                dp[index][rest] = dp[index + 1][rest] + (rest - arr[index]) < 0 ? 0 : dp[index + 1][rest - arr[index]];dp[index][rest] = dp[index + 1][rest] + (rest - arr[index] >= 0 ? dp[index + 1][rest - arr[index]] : 0);}}return dp[0][aim];}

測試代碼：

略

測試結果：

組成aim的方法數(shù)（每種張數(shù)無限）

題意：arr是面值數(shù)組，其中的值都是正數(shù)且沒有重復。再給定一個正數(shù)aim。
每個值都認為是一種面值，且認為張數(shù)是無限的。返回組成aim的方法數(shù)
例如：arr = {1,2}，aim = 4 方法如下：1+1+1+1、1+1+2、2+2
一共就3種方法，所以返回3。

解題思路：

• 大體思路和上邊相同，只不過子過程需要對要用多少張數(shù)進行遍歷
• 張數(shù)遍歷時循環(huán)條件為zhang * arr[index] <= rest，對應的dp改寫中也需要遍歷（如果不優(yōu)化的，優(yōu)化之后再說，這里應該是可以進行斜率優(yōu)化）

核心代碼：

遞歸：

public static int coinsWay(int[] arr, int aim) {if (arr == null || arr.length == 0 || aim < 0) {return 0;}return process(arr, 0, aim);
}public static int process(int[] arr, int index, int rest) {if(rest<0){return 0;}if(index==arr.length){return rest==0?1:0;}int ways=0;for (int zhang = 0; zhang*arr[index] < rest ; zhang++) {ways+=process(arr,index+1,rest-zhang*arr[index]);}return ways;
}

dp:

public static int dp(int[] arr, int aim) {if (arr == null || arr.length == 0 || aim < 0) {return 0;}int N = arr.length;int[][] dp = new int[N + 1][aim + 1];dp[N][0] = 1;for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {int ways=0;for (int zhang = 0; zhang*arr[index] < rest ; zhang++) {ways+=(rest-zhang*arr[index]<0)? 0: dp[index+1][rest-zhang*arr[index]];}dp[index][rest]=ways;}}return dp[0][aim];
}

測試代碼：

略

測試結果：

組成aim的方法數(shù)（每種張數(shù)有限）

題意：arr是貨幣數(shù)組，其中的值都是正數(shù)。再給定一個正數(shù)aim。每個值都認為是一張貨幣，認為值相同的貨幣沒有任何不同，返回組成aim的方法數(shù)

例如：arr = {1,2,1,1,2,1,2}，aim = 4方法：1+1+1+1、1+1+2、2+2
一共就3種方法，所以返回3

解題思路：

• 本題思路與上題類似，只是張數(shù)變成有限的了，對應的遍歷張數(shù)的條件多了一個
• 另外，本題不是給兩個數(shù)組一個張數(shù)組和值數(shù)組，所以我們還需要對數(shù)據(jù)進行預處理，封裝，并進行數(shù)據(jù)統(tǒng)計，并提供對應方法讓外部調(diào)用。
• 封裝構造方法初始化大小確定（我們給的）；getInfo是我們進行的詞頻統(tǒng)計，根據(jù)arr,涉及到containKey,put等方法

核心代碼：

遞歸代碼：

public static class Info {private int[] coins;private int[] zhangs;public Info(int[] coins, int[] zhangs) {this.coins = coins;this.zhangs = zhangs;}
}public static Info getInfo(int[] arr) {HashMap<Integer, Integer> map = new HashMap<>();for (int num : arr) {if (map.containsKey(num)) {map.put(num, map.get(num) + 1);} else {map.put(num, 1);}}int N = map.size();int[] coins = new int[N];int[] zhangs = new int[N];int index = 0;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {coins[index] = entry.getKey();zhangs[index] = entry.getValue();}Info info = new Info(coins, zhangs);return info;
}public static int coinsWay(int[] arr, int aim) {if (arr == null || arr.length == 0 || aim < 0) {return 0;}Info info = getInfo(arr);return process(info.coins, info.zhangs, 0, aim);
}public static int process(int[] coins, int[] zhangs, int index, int rest) {if (rest < 0) {return 0;}if (index == coins.length) {return rest == 0 ? 1 : 0;}int ways = 0;for (int zhang = 0; zhang < zhangs.length && (zhang * coins[index] < rest); zhang++) {ways += process(coins, zhangs, index + 1, rest - zhang * coins[index]);}return ways;
}

dp代碼：

public static int dp(int[] arr, int aim) {if (arr == null || arr.length == 0 || aim < 0) {return 0;}Info info = getInfo(arr);int[] coins = info.coins;int[] zhangs = info.zhangs;int N = coins.length;int[][] dp = new int[N + 1][aim + 1];dp[N][0] = 1;for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {int ways = 0;for (int zhang = 0; zhang < zhangs.length && (zhang * coins[index] < rest); zhang++) {ways += (rest - zhang * coins[index] < 0) ? 0 : dp[index + 1][rest - zhang * coins[index]];}dp[index][rest] = ways;}}return dp[0][aim];
}

測試代碼：略

測試結果：

組成aim的最小貨幣數(shù)（每張張數(shù)無限）

題意：arr是面值數(shù)組，其中的值都是正數(shù)且沒有重復。再給定一個正數(shù)aim。
每個值都認為是一種面值，且認為張數(shù)是無限的。返回組成aim的最少貨幣數(shù)。

解題思路：

• 還是需要對張數(shù)進行遍歷，只不過只有一個條件
• 接受結果值設為整數(shù)最大值，最終結果返回較小值
• 另外另外，邊界條件不滿足條件的值需要修改成最大值，不難咱們得犯大難了，遭老罪了！要不然你計算的時候把沒有組成aim的，但是張數(shù)更少的算里邊了，肯定錯啊；rest==0時，不需要貨幣，即使?jié)M足也不需要了，所以記得改成0

補充：

• 這里其實可以對數(shù)組按照貨幣值進行預處理/排序（使用迭代給sort傳比較器//優(yōu)先級隊列）
• 面值數(shù)組，不需要預處理，只需要用于降序排列的比較器

核心代碼：

遞歸代碼：

public static int minCoins(int[] arr, int aim) {if(aim==0){return 0;}if (arr == null || arr.length == 0 || aim < 0) {return Integer.MAX_VALUE;}return process(arr, 0, aim);
}public static int process(int[] arr, int index, int rest) {if (rest < 0) {return Integer.MAX_VALUE;}if (index == arr.length) {return rest == 0 ? 0 : Integer.MAX_VALUE;}int ans = Integer.MAX_VALUE;for (int zhang = 0; zhang * arr[index] < rest; zhang++) {int next = process(arr, index + 1, rest - zhang * arr[index]);if (next != Integer.MAX_VALUE && next > 0) {//要不然最大值加最大值可能滾成負數(shù)ans = Math.min(next, ans);}}return ans;
}

dp代碼：

public static int dp(int[] arr, int aim) {if (aim == 0) {return 0;}int N = arr.length;int[][] dp = new int[N + 1][aim + 1];dp[N][0] = 0;for (int j = 1; j <= aim; j++) {dp[N][j] = Integer.MAX_VALUE;}for (int index = N - 1; index >= 0; index--) {for (int rest = 0; rest <= aim; rest++) {int ans = Integer.MAX_VALUE;for (int zhang = 0; zhang * arr[index] < rest; zhang++) {int next = (rest - zhang * arr[index] < 0) ? Integer.MAX_VALUE : dp[index + 1][rest - zhang * arr[index]];if (next != Integer.MAX_VALUE && next > 0) {//要不然最大值加最大值可能滾成負數(shù)ans = Math.min(next, ans);}}dp[index][rest]=ans;}}return dp[0][aim];
}

測試代碼：略

測試結果：

從左到右嘗試模型總結1

改寫規(guī)則：

• 確定可變參數(shù)個數(shù)——dp是幾維表
• 確定可變參數(shù)的變化范圍——是0_N還是0N-1
• 預處理（邊界條件）
• 確定普遍位置怎么確定
• 邊界判斷——使用三目時一定要注意加括號😥
• 四個角中的哪個是最終結果

例題總結：

• 01背包——邊界判斷：超重是-1，沒裝夠/剛好是0；要和不要的兩種情況pk，要較小值
• 完全背包
• 多重背包
• 組成aim的方法數(shù)（每張認為是一種）——邊界判斷：超支/不夠都是0，aim=0時index<=arr.length都算是1;兩種情況不需要pk，直接相加返回
• 組成aim的方法數(shù)（每種張數(shù)無限）——邊界判斷：超支/不夠都是0，aim=0時index<=arr.length都算是1;不是兩種情況了，對有效的張數(shù)（一個條件）進行遍歷，總方法相加
• 組成aim的方法數(shù)（每種張數(shù)有限）——邊界判斷：超支/不夠都是0，aim=0時index<=arr.length都算是1;不是兩種情況了，對有效的張數(shù)（兩個條件）進行遍歷，總方法相加
• 組成aim的最小貨幣數(shù)（每張張數(shù)無限）——邊界條件判斷：初值都為最大值，除了aim=0時，遞歸那aim=0一定在非法條件的前邊，next值有效的判斷；兩種情況pk，要最小的

三種dp解法背包問題區(qū)別：

略

前三種dp解法貨幣數(shù)組區(qū)別：

注：這里返回的都是方法數(shù)，肯定是越多越好，不涉及邊界值返回的系列問題。

1. 貨幣數(shù)組類型決定了是否需要張數(shù)遍歷（面值 不用）
2. 張數(shù)有限無限決定了張數(shù)遍歷的條件是1個還是兩個
3. 一般都是index倒序，rest正序

注：區(qū)分面值數(shù)組、貨幣數(shù)組

前者是天然去重，后者可能存在相同的，看題目設定決定是否需要進行預處理

另本類型開頭的那種，其實也算是面值數(shù)組了。

兩種情況了，對有效的張數(shù)（一個條件）進行遍歷，總方法相加

• 組成aim的方法數(shù)（每種張數(shù)有限）——邊界判斷：超支/不夠都是0，aim=0時index<=arr.length都算是1;不是兩種情況了，對有效的張數(shù)（兩個條件）進行遍歷，總方法相加
• 組成aim的最小貨幣數(shù)（每張張數(shù)無限）——邊界條件判斷：初值都為最大值，除了aim=0時，遞歸那aim=0一定在非法條件的前邊，next值有效的判斷；兩種情況pk，要最小的

三種dp解法背包問題區(qū)別：

略

前三種dp解法貨幣數(shù)組區(qū)別：

注：這里返回的都是方法數(shù)，肯定是越多越好，不涉及邊界值返回的系列問題。

1. 貨幣數(shù)組類型決定了是否需要張數(shù)遍歷（面值 不用）
2. 張數(shù)有限無限決定了張數(shù)遍歷的條件是1個還是兩個
3. 一般都是index倒序，rest正序

注：區(qū)分面值數(shù)組、貨幣數(shù)組

前者是天然去重，后者可能存在相同的，看題目設定決定是否需要進行預處理

另本類型開頭的那種，其實也算是面值數(shù)組了。