给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。 数据范围:数组长度满足 ,数组中的数和 target 大小满足-笔试面试资料

这是qklbishe.com第19079 篇笔试面试资料
提供答案分析,通过本文《给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。
数据范围:数组长度满足 ,数组中的数和 target 大小满足-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。
数据范围:数组长度满足 给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。          数据范围:数组长度满足  ,数组中的数和 target 大小满足 ,数组中的数和 target 大小满足 给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。          数据范围:数组长度满足  ,数组中的数和 target 大小满足
Java

给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。          数据范围:数组长度满足  ,数组中的数和 target 大小满足 零葬

老套路,暴力递归->记忆化搜索->动态规划

暴力递归->记忆化搜索

从左往右尝试,depth表示当前第depth个面额及其之后的面额可以随意使用,rest为还剩下多少钱要凑。在递归的过程中有如下三种情况:
  1. rest=0,就表示形成了一种有效的方案;
  2. rest<0,当前的凑钱方案不合法,直接返回0;
  3. rest>0,使用递归从当前depth开始的面额继续凑目标值。

代码就不详细写了,直接用缓存法改一版记忆化搜索,防止递归展开的过程中重复计算。

private int recurrent(int[] nums, int depth, int rest, int[][] mem) {     if(rest < 0){         return 0;     }     if(rest == 0){         return 1;     }     if(mem[depth][rest] > 0) return mem[depth][rest];     for(int i = depth; i < nums.length; i++){         mem[depth][rest] += recurrent(nums, i, rest - nums[i], mem);     }     return mem[depth][rest]; }

动态规划

然后根据递归的逻辑可以修改出动态规划的过程,dp[i][j]表示利用从i到最后一种面额凑j能有多少种方案。根据递归函数中的递归头确定base case,dp数组的第一列为1。根据递归中depthrest的取值可以发现dp[i][j]依赖左边和下面的值,因此从下往上,从左往右填表。

import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param target int整型       * @param nums int整型一维数组       * @return int整型      */     public int change (int target, int[] nums) {         // write code here         int n = nums.length;         int[][] dp = new int[n][target + 1];         for(int i = 0; i < n; i++){             dp[i][0] = 1;         }         for(int i = n - 1; i >= 0; i--){             for(int j = nums[i]; j <= target; j++){                 dp[i][j] = (i < n - 1? dp[i + 1][j]: 0) + dp[i][j - nums[i]];             }         }         return dp[0][target];     } }

最后我们注意到,dp[i][j]只依赖其下一行及左边的值,因此还可以进行空间压缩,dp用一维数组就可以,这也就是我们经常看到的背包问题解法。

import java.util.*;   public class Solution {     /**      * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可      *      *       * @param target int整型       * @param nums int整型一维数组       * @return int整型      */     public int change (int target, int[] nums) {         // write code here         int n = nums.length;         int[] dp = new int[target + 1];         dp[0] = 1;         for(int i = n - 1; i >= 0; i--){             for(int j = nums[i]; j <= target; j++){                 dp[j] += dp[j - nums[i]];             }         }         return dp[target];     } }

今天 16:07:43 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 给定一个整数数组 nums 表示不同数额的硬币和一个正整数 target 表示总金额,请你计算并返回可以凑出总金额的的组合数。如果凑不出 target 则返回 0。 数据范围:数组长度满足 ,数组中的数和 target 大小满足-笔试面试资料

提供最优质的资源集合

立即查看 了解详情