本文主要是介绍算法训练营第四十六天 | 卡码网52 携带研究材料、LeetCode 518 零钱兑换II、LeetCode 377 组合总和IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
写在前面
这次算法训练营题目，其实完全是按照代码随想录一路跟着来的，上面也有更好的、讲得更清楚的题解，有需要的小伙伴可以去那里看。
我这里是之前已经大体刷过一遍，为了应对有可能会考到的面试题，现在在跟着一个专门的、要花钱的训练营补完笔记，加深理解。
下面开始今天的刷题和笔记。
卡码网 52
这题是完全背包问题的典型，完全背包也就是每个物品可以取无限次。
如果用二维dp的话，我们每个物品都要再加一个在能取次数内几个次数的循环比较。
而用一维dp数组的内层正向遍历就能很好地解决这个问题，所以我们修改下内层遍历顺序就行了。
代码如下：
import java.util.*;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int bagSize = in.nextInt();int[] w = new int[n];int[] v = new int[n];for (int i = 0; i < n; i++) {w[i] = in.nextInt();v[i] = in.nextInt();}int[] dp = new int[bagSize + 1];for (int i = 0; i < n; i++) {for (int j = 0; j <= bagSize; j++) {if (j >= w[i])dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);}}System.out.println(dp[bagSize]);}
}LeetCode 518 零钱兑换II
这题基本还是完全背包的思路，不过是计算方法数类型的问题。需要改动的地方主要是初始化这一块，要将dp[0]置为1，然后利用滚动数组的特性，可以让每种方法都计数为1。
代码如下：
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = 0; j <= amount; j++) {if (j >= coins[i])dp[j] += dp[j - coins[i]];}}return dp[amount];}
}如果是二维dp数组的话，每一轮中的dp[i][0]都要设置为1。递推逻辑也要稍微变化下。
代码如下：
class Solution {public int change(int amount, int[] coins) {int[][] dp = new int[coins.length][amount + 1];for (int i = 0; i < coins.length; i++) dp[i][0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = 0; j <= amount; j++) {if (j >= coins[i])if (i == 0) dp[i][j] += dp[i][j - coins[i]];else dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];else if (i == 0) continue;else dp[i][j] = dp[i - 1][j];}}return dp[coins.length - 1][amount];}
}LeetCode 377 组合总和IV
这题是排列问题，上面一题是组合问题。两个问题在遍历顺序上有较大差别。这是方法数问题在dp这一块的特殊问题，如果只是单纯的求总价值的话就没有这个问题了。
解决方法是将内重外重循环反过来，这样在每个背包重量下，放入某个价值的物品最后构成的不同顺序的方法都会被计算进去。
比如这组数据
两重循环顺序反过来后就是这样
原先是这样
确实可以看出由遍历顺序引起的放入次数的问题，这是由于原先总是按照物品下标从小到大放入，顺序倒转后有可能下标较大的物品先被放入造成了次序上的不一致。而且也可以看出这其实也是完全背包这一块的特殊问题，01背包问题很少会问到排列。
代码如下：
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1;for (int j = 0; j <= target; j++) {for (int i = 0; i < nums.length; i++) {if (j >= nums[i]) dp[j] += dp[j - nums[i]];System.out.print(dp[j] + " ");}System.out.println();}return dp[target];}
}这篇关于算法训练营第四十六天 | 卡码网52 携带研究材料、LeetCode 518 零钱兑换II、LeetCode 377 组合总和IV的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
