算法8.从暴力递归到动态规划1

算法|8.从暴力递归到动态规划1

目前感觉，背包问题和货币数组问题本质相同，货币的与dp相关的三种代码写完了，快复习不完了，背包暂时先不写了，回头再写，补充，再总结，结合那个C++大神的文章再弄。

背包类问题

目前来讲，我接触到的背包问题有四种分别是01背包、完全背包、多重背包、以及部分背包。背包问题都属于NP问题（非直接求解问题），前三种一般使用动态规划进行求解，后一种一般使用贪心求解。

01背包

题意：给定两个长度都为N的数组weights和values，weights[i]和values[i]分别代表 i号物品的重量和价值。给定一个正数bag，表示一个载重bag的袋子，装的物品不能超过这个重量。返回能装下的最大价值

解题思路：

• 先写出递归版本，然后对照着改dp。
• 要与不要。结果越大越好，是正向决策，同时使用的累加。
• 参数设置：重量数组w、价值数组v、当前决策到的坐标index、背包剩余的空间rest
• 可变参数为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的背包，数量为s[i]。第 i件物品的体积是 v[i]，价值是w[i] .求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

解题思路：

核心代码：

测试代码：

测试结果：

货币类问题

组成aim的方法数（每张认为是一种）

题意：arr是货币数组，其中的值都是正数。再给定一个正数aim。
每个值都认为是一张货币，即便是值相同的货币也认为每一张都是不同的，
返回组成aim的方法数。例如：arr = {1,1,1}，aim = 2。
第0个和第1个能组成2，第1个和第2个能组成2，第0个和第2个能组成2
一共就3种方法，所以返回3

解题思路：

• 这一题其实和01背包问题很像，只是这个是要求正好组成aim，01背包则是不超过的方法数
• 所以这里我们只需要在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的方法数（每种张数无限）

题意：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
每个值都认为是一种面值，且认为张数是无限的。返回组成aim的方法数
例如：arr = {1,2}，aim = 4 方法如下：1+1+1+1、1+1+2、2+2
一共就3种方法，所以返回3。

解题思路：

• 大体思路和上边相同，只不过子过程需要对要用多少张数进行遍历
• 张数遍历时循环条件为zhang * arr[index] <= rest，对应的dp改写中也需要遍历（如果不优化的，优化之后再说，这里应该是可以进行斜率优化）

核心代码：

递归：

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的方法数（每种张数有限）

题意：arr是货币数组，其中的值都是正数。再给定一个正数aim。每个值都认为是一张货币，认为值相同的货币没有任何不同，返回组成aim的方法数

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

解题思路：

• 本题思路与上题类似，只是张数变成有限的了，对应的遍历张数的条件多了一个
• 另外，本题不是给两个数组一个张数组和值数组，所以我们还需要对数据进行预处理，封装，并进行数据统计，并提供对应方法让外部调用。
• 封装构造方法初始化大小确定（我们给的）；getInfo是我们进行的词频统计，根据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的最小货币数（每张张数无限）

题意：arr是面值数组，其中的值都是正数且没有重复。再给定一个正数aim。
每个值都认为是一种面值，且认为张数是无限的。返回组成aim的最少货币数。

解题思路：

• 还是需要对张数进行遍历，只不过只有一个条件
• 接受结果值设为整数最大值，最终结果返回较小值
• 另外另外，边界条件不满足条件的值需要修改成最大值，不难咱们得犯大难了，遭老罪了！要不然你计算的时候把没有组成aim的，但是张数更少的算里边了，肯定错啊；rest==0时，不需要货币，即使满足也不需要了，所以记得改成0

补充：

• 这里其实可以对数组按照货币值进行预处理/排序（使用迭代给sort传比较器//优先级队列）
• 面值数组，不需要预处理，只需要用于降序排列的比较器

核心代码：

递归代码：

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) {//要不然最大值加最大值可能滚成负数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) {//要不然最大值加最大值可能滚成负数ans = Math.min(next, ans);}}dp[index][rest]=ans;}}return dp[0][aim];
}

测试代码：略

测试结果：

从左到右尝试模型总结1

改写规则：

• 确定可变参数个数——dp是几维表
• 确定可变参数的变化范围——是0_N还是0N-1
• 预处理（边界条件）
• 确定普遍位置怎么确定
• 边界判断——使用三目时一定要注意加括号😥
• 四个角中的哪个是最终结果

例题总结：

• 01背包——边界判断：超重是-1，没装够/刚好是0；要和不要的两种情况pk，要较小值
• 完全背包
• 多重背包
• 组成aim的方法数（每张认为是一种）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;两种情况不需要pk，直接相加返回
• 组成aim的方法数（每种张数无限）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;不是两种情况了，对有效的张数（一个条件）进行遍历，总方法相加
• 组成aim的方法数（每种张数有限）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;不是两种情况了，对有效的张数（两个条件）进行遍历，总方法相加
• 组成aim的最小货币数（每张张数无限）——边界条件判断：初值都为最大值，除了aim=0时，递归那aim=0一定在非法条件的前边，next值有效的判断；两种情况pk，要最小的

三种dp解法背包问题区别：

略

前三种dp解法货币数组区别：

注：这里返回的都是方法数，肯定是越多越好，不涉及边界值返回的系列问题。

1. 货币数组类型决定了是否需要张数遍历（面值 不用）
2. 张数有限无限决定了张数遍历的条件是1个还是两个
3. 一般都是index倒序，rest正序

注：区分面值数组、货币数组

前者是天然去重，后者可能存在相同的，看题目设定决定是否需要进行预处理

另本类型开头的那种，其实也算是面值数组了。

两种情况了，对有效的张数（一个条件）进行遍历，总方法相加

• 组成aim的方法数（每种张数有限）——边界判断：超支/不够都是0，aim=0时index<=arr.length都算是1;不是两种情况了，对有效的张数（两个条件）进行遍历，总方法相加
• 组成aim的最小货币数（每张张数无限）——边界条件判断：初值都为最大值，除了aim=0时，递归那aim=0一定在非法条件的前边，next值有效的判断；两种情况pk，要最小的

三种dp解法背包问题区别：

略

前三种dp解法货币数组区别：

注：这里返回的都是方法数，肯定是越多越好，不涉及边界值返回的系列问题。

1. 货币数组类型决定了是否需要张数遍历（面值 不用）
2. 张数有限无限决定了张数遍历的条件是1个还是两个
3. 一般都是index倒序，rest正序

注：区分面值数组、货币数组

前者是天然去重，后者可能存在相同的，看题目设定决定是否需要进行预处理

另本类型开头的那种，其实也算是面值数组了。