首页 > 其他分享 >Leetcode(剑指offer专项训练)——DP专项(6)

Leetcode(剑指offer专项训练)——DP专项(6)

时间:2023-04-02 16:45:10浏览次数:47  
标签:专项 target nums int sum num dp Leetcode DP

排序的数目

题目

给定一个由 不同 正整数组成的数组 nums ,和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次,但是顺序不同的序列被视作不同的组合。
题目数据保证答案符合 32 位整数范围。
链接

无效DFS

DFS不剪枝的情况下,没有办法在有限时间内结束相应的任务

class Solution {
public:
    int ans=0;
    int n;
    void dfs(int sum,vector<int>&nums,int & target){
        if(sum>target){
            return;
        }else if(sum==target){
            ans++;
        }
        for(int i=0;i<n;i++){
            dfs(sum+nums[i],nums,target);
        }
    }
    int combinationSum4(vector<int>& nums, int target) {
        n=nums.size();
        for(int i=0;i<n;i++){
            dfs(nums[i],nums,target);
        }
        return ans;
    }
};

题解

思路:动态规划
初始化 dp[0]=1
遍历 j 从 1 到target,对于每个 j,进行如下操作:
遍历数组 nums 中的每个元素 num,当 num≤j 时,将 dp[j−num] 的值加到 dp[j]。
最终得到 dp[target]
dp[target] 的值即为答案

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n=nums.size();
        vector<int>dp(target+1,0);
        dp[0]=1;//和为0只有一种方式
        for(int j=1;j<=target;j++){
            for(auto num:nums){
                if(j>=num&&dp[j-num]<INT_MAX-dp[j]){//c++需要注意int溢出的问题,所以要添加dp[j-num]<INT_MAX-dp[j]作为判断条件
                    dp[j]+=dp[j-num];
                }
            }
        }
        return dp[target];
    }
};

标签:专项,target,nums,int,sum,num,dp,Leetcode,DP
From: https://www.cnblogs.com/SaltyCheese/p/17280730.html

相关文章

  • Leetcode(剑指offer专项训练)——DP专项(5)
    最少的硬币数目给定不同面额的硬币coins和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。你可以认为每种硬币的数量是无限的。链接完全背包问题思路:主要是要自己推出动态转移方程\[F(i)=mi......
  • 【DP】LeetCode 64. 最小路径和
    题目链接64.最小路径和思路分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律表示状态假设到了右下角,考虑一下我们要存储的信息走到最后坐标的最小步数当前坐标的信息,用来判断是否走到了右下角很容易联想到使用......
  • 【DP】LeetCode 70. 爬楼梯
    题目链接70.爬楼梯思路分析动态规划题目的时候只需要考虑最后一个阶段,因为所有的阶段转化都是相同的,考虑最后一个阶段容易发现规律表示状态假设走到了最后一层台阶,考虑一下我们要存储的信息:走到这最后一层台阶的方法数当前台阶数,用于判断是否走到了最后一层台阶这时候......
  • [LeetCode] 1338. Reduce Array Size to The Half 数组大小减半
    Youaregivenanintegerarray arr.Youcanchooseasetofintegersandremovealltheoccurrencesoftheseintegersinthearray.Return theminimumsizeofthesetsothat atleast halfoftheintegersofthearrayareremoved.Example1:Input:arr=......
  • Leetcode(剑指offer专项训练)——DP专项(4)
    加减的目标值给定一个正整数数组nums和一个整数target。向数组中的每个整数前添加 '+'或'-',然后串联起所有整数,可以构造一个表达式:例如,nums=[2,1],可以在2之前添加'+',在1之前添加'-',然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算......
  • 代码随想录Day17-Leetcode110.平衡二叉树,257. 二叉树的所有路径,404.左叶子之和
    110.平衡二叉树题目链接:https://leetcode.cn/problems/balanced-binary-tree/一个显然但似乎不太高效的方法是:通过递归获取左右子树高度,判断差;然后递归判断左右结点;那么一个显然的改进就是后序遍历/***Definitionforabinarytreenode.*functionTreeNode(val......
  • 关于网络通信中TCP/UDP的端口范围-以及在Linux系统中的使用权限说明
    关于TCP/UDP的端口号的范围都是0~65535 根据IANA定义,可以参考如下链接:https://www.iana.org/assignments/service-names-port-numbers/service-names-port-numbers.xhtmlIANA将这些端口分成了3类,LastUpdated2023-03-30Portnumbersareassignedinvariousways,based......
  • 调试freeradius时遇到的 线程池以及udp相关问题
    调试线程池过程中遇到了一个return和pthread_exit的问题;google一下发现右如下概念首先,return语句和pthread_exit()函数的含义不同,return的含义是返回,它不仅可以用于线程执行的函数,普通函数也可以使用;pthread_exit()函数的含义是线程退出,它专门用于结束某个线程的执行。在主......
  • leetcode876. 链表的中间结点
      876. 链表的中间结点方法一:最简单的做法,先求出整个链表的长度,再求1/2处节点的位置。/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx)......
  • leetcode-733-easy
    FloodFillAnimageisrepresentedbyanmxnintegergridimagewhereimage[i][j]representsthepixelvalueoftheimage.Youarealsogiventhreeintegerssr,sc,andcolor.Youshouldperformafloodfillontheimagestartingfromthepixelimage[sr......