int[] memo; int coinChange(int[] coins, int amount) { memo = new int[amount + 1]; // 备忘录初始化为⼀个不会被取到的特殊值，代表还未被计算 Arrays.fill(memo, -666);return dp(coins, amount); } int dp(int[] coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; // 查备忘录，防⽌重复计算 if (memo[amount] != -666) return memo[amount]; int res = Integer.MAX_VALUE; for (int coin : coins) { // 计算⼦问题的结果 int subProblem = dp(coins, amount - coin); // ⼦问题⽆解则跳过 if (subProblem == -1) continue; // 在⼦问题中选择最优解，然后加⼀ res = Math.min(res, subProblem + 1); } // 把计算结果存⼊备忘录 memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res; return memo[amount]; }

这段代码实现的是使用动态规划算法解决零钱兑换问题。其中，memo数组是备忘录，用于记录已经计算过的子问题的结果，避免重复计算。具体实现步骤如下：

1. 初始化memo数组为一个不会被取到的特殊值，代表还未被计算。
2. 调用dp函数，传入coins数组和amount金额。
3. 如果amount为0，直接返回0；
4. 如果amount小于0，说明当前组合不可行，返回-1；
5. 查备忘录，如果memo[amount]不等于特殊值，说明已经计算过，直接返回memo[amount]。
6. 初始化res为最大值，遍历coins数组。
7. 对于每个coin，通过递归调用dp函数计算子问题的结果subProblem。
8. 如果子问题无解，则跳过当前coin，继续遍历下一个coin。
9. 在子问题中选择最优解，然后加1，更新res。
10. 将计算结果存入备忘录memo[amount]中。
11. 返回memo[amount]作为当前组合的最优解。

该算法的时间复杂度为O(amount*N)，其中N为coins数组的长度。由于使用了备忘录，避免了重复计算，因此该算法的空间复杂度为O(amount)。

相关问题

解释代码int[][] memo; int numTrees(int n) { // 备忘录的值初始化为 0 memo = new int[n + 1][n + 1]; return count(1, n); }

这段代码是一个动态规划算法用于计算n个节点的二叉搜索树的数量。其中，声明了一个二维数组memo作为备忘录，用于记录每个子问题的解，避免重复计算。具体来说，memo[i][j]表示以i为根节点，j为右边界的二叉搜索树的数量。在函数count中，通过递归的方式，将问题分解成子问题，并从备忘录中查找是否已经计算过该子问题的解，如果已经计算过，则直接返回备忘录中存储的值，否则继续递归计算。最终，将所有子问题的解加起来即可得到n个节点的二叉搜索树的数量。

解释代码int[][] memo; int numTrees(int n) { // 备忘录的值初始化为 0 memo = new int[n + 1][n + 1]; return count(1, n); } int count(int lo, int hi) { if (lo > hi) return 1; // 查备忘录 if (memo[lo][hi] != 0) { return memo[lo][hi]; } int res = 0; for (int mid = lo; mid <= hi; mid++) { int left = count(lo, mid - 1); int right = count(mid + 1, hi); res += left * right; } // 将结果存入备忘录 memo[lo][hi] = res; return res; }

这段代码实现了一个递归函数numTrees，用于计算n个节点的二叉搜索树的数量。为了避免重复计算，使用了备忘录memo来保存已经计算过的结果。

具体来说，函数count(lo, hi)用于计算从lo到hi的节点构成的二叉搜索树的数量。如果lo>hi，则返回1，因为空树也算一棵树。如果备忘录memo中已经有了这个范围的计算结果，则直接返回结果。否则，对于每个mid（即根节点），计算左右子树的数量，然后将左右子树的数量相乘，即可得到以mid为根节点的二叉搜索树的数量。最后，将所有以不同节点为根节点的二叉搜索树的数量相加，得到从lo到hi的节点构成的所有二叉搜索树的数量。同时，将这个结果存入备忘录memo中，以便后续使用。

在函数numTrees中，先将备忘录memo初始化为0，然后调用count(1, n)计算n个节点构成的所有二叉搜索树的数量。