首页 > 其他分享 >甲骨文面试题【动态规划】力扣377.组合总和IV

甲骨文面试题【动态规划】力扣377.组合总和IV

时间:2024-07-17 17:27:41浏览次数:15  
标签:面试题 target nums int MAX IV 力扣 num dp

给你一个由 不同 整数组成的数组 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

在这里插入图片描述


看逻辑图把逻辑理清楚,弄明白dp[i]储存的是什么,然后为什么要减去num的目的是什么。(拿图请标明出处)
在这里插入图片描述

在这里插入图片描述

代码

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;
        for(int i=1;i<=target;i++){
            for(int num : nums){
                if(num <= i && dp[i-num] < INT_MAX - dp[i]){
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
};

注意dp[i-num] < INT_MAX - dp[i]不可以写成
dp[i-num] + dp[i] < INT_MAX ,因为先进行求和再检查是不安全的,如果求和大于INT_MAX,会发生溢出,导致结果变为负数或者一个不可预测的值,可能会导致检查通过。

标签:面试题,target,nums,int,MAX,IV,力扣,num,dp
From: https://blog.csdn.net/sjsjs11/article/details/140498962

相关文章

  • Divide Interval 题解
    背景太逊了,调了三次才调出来,所以写篇题解寄念。LC好睿智题意给你两个数\(a,b\),现在要从\(a\)跑到\(b\),每次可以将当前的\(a\)拆分成\(2^n\timesm(n,m\inN)\)的形式,并将它变成\(2^n\times(m+1)\)。问最少变几次能跑到\(b\),输出次数和每次变化前后\(a\)的值。分......
  • CSS Case Insensitive Attribute Selector All In One
    CSSCaseInsensitiveAttributeSelectorAllInOneCSS大小写敏感的属性选择器/*casesensitive,onlymatches"case_sensitive"*/[class=case_sensitive]{background:pink;}Addingaspacebeforetheiflagtotheattributeselectorbracketswillmak......
  • 数据类型及扩展面试题
    publicclassdemo3{publicstaticvoidmain(String[]args){整数拓展进制二进制(0b)八进制(0)十进制十六进制(ox)inti=10;inti1=010;//八进制inti2=0xC;//十六进制0~9A~FSystem.out.println(i);System.out.println(i1);System.out.......
  • 前端—面试题1
    前端—今日面试题var、let和const的区别var的特点let的特点const的特点var、let和const的区别简介:能用const的情况下尽量使用const,大多数情况使用let,避免使用var技巧:const一般声明引用数据类型,let一般声明基本数据类型区别:varletconst变量提升√块级作用域√√......
  • CodeForces Round 898 (div 4) H题解析
     CodeForcesRound898(div4)H.Mad City                           大致思路   对于有n条边和n个点,说明这个图里面只有一个环并且两人同时开始和结束移动,所以可以得到当Valeriu进入到这个图里面的唯一......
  • Codeforces Round 958 (Div. 2)
    题目链接:CodeforcesRound958(Div.2)总结:C因为常数没转\(longlong\)\(wa\)两发,难绷。A.SplittheMultisetfag:模拟Description:给定一个\(n\)和一个\(k\),每次可以将\(n\)减掉一个数\(u\),然后插入\(x\)个数,\(x<=k\),并且插入的数之和等于\(u\)。求将其转化为全\(1\)的最......
  • Codeforces Round 957 (Div. 3)
    知识点1.几个数相乘时,更小的数增加会比更大的数增加得到的乘积来得大题解A.OnlyPluses1.几个数相乘时,当更小的数增大时,得到的乘积会比更大的数增大来得大,也就是更小的数字权重会比较大,那么在5次+1的过程中,每次找最小值++即可#include<bits/stdc++.h>#defineintlonglon......
  • 力扣刷题练习九 【234.回文链表】
    前言链表练习题【234.回文链表】。回顾链表知识,做题练习。一、【234.回文链表】题目阅读给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false。示例1:输入:head=[1,2,2,1]输出:true示例2:输入:head=[1,2]输出:false......
  • Codeforces Round 898 (Div. 4)(A~H)
    目录A.ShortSortB.GoodKidC.TargetPracticeD.1DEraserE.BuildinganAquariumF.MoneyTreesG.ABBCorBACBH.MadCityA.ShortSortProblem-A-Codeforces暴力枚举每个位置的交换即可。#include<iostream>#include<algorithm>#include<queue......
  • Hive自定义函数编写方法(含源代码解读,超详细,易理解)
    一、Hive自定义函数介绍        1.内置函数        Hive自带了一些函数。比如:max/min等,但是数量有限,自己可以通过自定义UDF来方便的扩展。2.自定义函数        当Hive提供的内置函数无法满足你的业务处理需要时,此时就可以考虑使用用户自定义函数(UD......