377. 组合总和 Ⅳ
给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
 
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
 
请注意,顺序不同的序列被视作不同的组合。
 
因此输出为 7。
进阶:
如果给定的数组中含有负数会怎么样?
问题会产生什么变化?
我们需要在题目中添加什么限制来允许负数的出现?
思路:类似于零钱兑换,用dp来做。

leetcode-零钱兑换—int溢出

比如4块钱,寻找nums[i]+(4-target[i])的组合
 
class Solution {

    public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int len=nums.length;
int dp[]=new int[target+1];
dp[0]=1; //就是设置成dp[0]=1!!!
for(int i=1;i<=target;i++){
for(int j=0;j<len;j++){
if(i>=nums[j])dp[i]+=dp[i-nums[j]]; //
}
}
return dp[target];
} }

最新文章

  1. CF 208A Dubstep(简单字符串处理)
  2. Studying-Swift :Day01
  3. [SQL]不知道
  4. MS-SQLSERVER中的MSDTC不可用解决方法
  5. php_DWZ-JUI中碰到的问题解决方法详解(thinkphp+dwz)
  6. error C2664: “UINT GetDriveTypeW(LPCWSTR)”: 无法将参数 1 从“char [5]”转换为“LPCWSTR”
  7. selinux导致docker启动失败
  8. WebSocket协议详解与c++&amp;c#实现
  9. android studio 撤销和恢复
  10. 【洛谷P2660烤鸡】
  11. JIRA的邮件通知
  12. BZOJ3926 [Zjoi2015]诸神眷顾的幻想乡 字符串 SAM
  13. 排序算法系列:选择排序算法JAVA版(靠谱、清晰、真实、可用、不罗嗦版)
  14. git的配置操作
  15. nodejs(五)同步异步--BLOCKING THE EVENT LOOP
  16. Perl 获得当前路径
  17. Archlinux Setup AUR
  18. Shape of passed values is (3490, 21), indices imply (3469, 21)
  19. markdown常用命令(持续整理更新...)
  20. sping boot 入门

热门文章

  1. STM32F103片外运行代码分析
  2. AltiumDesigner16笔记
  3. AJAX上传文件到服务器
  4. Jquery 操作 select 的操作指南
  5. HTML如何禁止input输入
  6. HDU Ellipse(simpson积分)
  7. chromium之ref_counted
  8. Linux中Elasticsearch集群部署
  9. canvas 将html绘制图片 生成图片链接
  10. hadoop的自定义分组实现 (Partition机制)