南通做网站多少钱,互联网推广销售,自我介绍网页设计代码,做网站怎么挣钱赚钱题意理解#xff1a; 给你一个由 不同 整数组成的数组 nums #xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 这道题目和凑零钱是一样的#xff0c;需要求使用指定元素#xff08;纸币… 题意理解 给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 这道题目和凑零钱是一样的需要求使用指定元素纸币凑出target(指定金额)有多少种方式。 此处元素是可以重复使用的所以该问题是一个完全背包问题。 解题思路 首先了解此题目是一个完全背包问题所以遍历背包时正序可以保证元素无限次使用。 其次确定题目求得是有多少种方式而不是重量或最大价值该题目不是一个纯背包问题。 由于我们要求组成target得不同方式12 和21 被看作是两种方式所以这里求的是排列数对于顺序有要求。 根据之前的总结 求组合数先物体后背包 求排列数先背包后物体 所以我们选择第二种 1.动态规划解题 public int combinationSum4(int[] nums, int target) {if(nums.length0) return 0;int[] dpnew int[target1];Arrays.fill(dp,0);dp[0]1;for(int j1;jtarget;j){for(int i0;inums.length;i){if(nums[i]j){dp[j]dp[j-nums[i]];}}}return dp[target];}
2.分析 时间复杂度O(n^2) 空间复杂度O(n)
