首页 > 其他分享 >动态规划-背包问题-完全背包问题:leetcode 377. 组合总和 Ⅳ

动态规划-背包问题-完全背包问题:leetcode 377. 组合总和 Ⅳ

时间:2023-06-28 21:11:26浏览次数:44  
标签:背包 target 组合 nums int 377 leetcode dp

1. 题目

读题

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

 

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
示例 2:

输入:nums = [9], target = 3
输出:0

 

考查点

动态规划-背包问题-完全背包问题 

2. 解法

思路

  • 定义dp 数组:dp[i]  表示 和为 i  有多少种组合
  • 初始值 :dp[0] = 1  表示和为0 只有1种组合,都不选 
  • 状态转移公式: 迭代nums 值  累加 :dp[i] = dp[i]+ dp[i-nums[j]] 

代码逻辑

 

具体实现

public class CombinationSumIV {

public static void main(String[] args) {
int[] nums = new int[]{1,2,3};
int target = 4;
System.out.println(combinationSum4(nums,target));
}

public static int combinationSum4(int[] nums, int target) {

int[] dp = new int[target + 1];
dp[0] = 1;

for (int i = 0; i <= target; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] = dp[i] + dp[i - num];
}
}
}

return dp[target];

}
}

 

3. 总结

标签:背包,target,组合,nums,int,377,leetcode,dp
From: https://www.cnblogs.com/shoshana-kong/p/17512580.html

相关文章

  • 7-010-(LeetCode- 518) 零钱兑换II
    1.题目读题518.零钱兑换II给你一个整数数组coins表示不同面额的硬币,另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回0。假设每一种面额的硬币有无限个。题目数据保证结果符合32位带符号整数。......
  • 动态规划 完全背包问题 -游戏最大伤害
     1.题目读题 游戏角色,有技能列表和魔法值,求能造成的最大伤害,例如:输入skill_list:[{mana_cost:10,damage:10},{mana_cost:12,damage:13}],current_mana:20,输出max_damage:20输入skill_list:[{mana_cost:10,damage:10},{mana_cost:12,damage:13}],current......
  • PACM Team (牛客多校) (DP 01背包, 维度较多)
    题目大意:给出n个物品,物品有4个空间值,然后有一个权值问在不超过最大的空间值时,最大的权值  思路:一开始想了很多其他思路没有想出来开始广搜算法,发现dp可以解决(注意看数据范围,是满足的)遇到奇怪的题,就试试dp,特别在数据范围很小的时候 ......
  • #yyds干货盘点# LeetCode程序员面试金典:重排链表
    题目:给定一个单链表L的头节点head,单链表L表示为:L0→L1→…→Ln-1→Ln请将其重新排列后变为:L0→Ln→L1→Ln-1→L2→Ln-2→…不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例1:输入:head=[1,2,3,4]输出:[1,4,2,3]示例2:输入:head......
  • LeetCode C++:HashTable篇
    1、TwoSumGivenanarrayofintegersnums andanintegertarget,returnindicesofthetwonumberssuchthattheyadduptotarget.Youmayassumethateachinputwouldhaveexactlyonesolution,andyoumaynotusethesameelementtwice.Youcanreturn......
  • leetcode 21. 合并两个有序链表
    直接合并即可这道题是简单题,直接合并即可/**Definitionforsingly-linkedlist.publicclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=nex......
  • [LeetCode] 1071. Greatest Common Divisor of Strings
    Fortwostrings s and t,wesay"t divides s"ifandonlyif s=t+...+t (i.e., t isconcatenatedwithitselfoneormoretimes).Giventwostrings str1 and str2,return thelargeststring x suchthat x dividesboth str1 and str2.Exam......
  • LeetCode —— 滑动窗口
    904. 水果成篮用一个Map记录当前窗口的情况: key-水果种类数value-这个水果种类在当前滑动窗口里出现的次数维持一个left指针到right指针的滑动窗口每次right右移一位,将新加入窗口的  fruits[right]这个种类放到map里,并将该种类计数+1如果当前窗口水果......
  • [LeetCode] 2485. Find the Pivot Integer
    Givenapositiveinteger n,findthe pivotinteger x suchthat:Thesumofallelementsbetween 1 and x inclusivelyequalsthesumofallelementsbetween x and n inclusively.Return thepivotinteger x.Ifnosuchintegerexists,return -1.......
  • LeetCode 128. 最长连续序列
    为什么这题我都不会,脑袋有点累,状态真差classSolution{public:intlongestConsecutive(vector<int>&nums){unordered_set<int>s(nums.begin(),nums.end());//记录数字是否出现过intres=0;for(autoi:nums)//枚举每个数字,查看以当前数字......