算法第十一天-组合总和Ⅳ

组合总和Ⅳ

题目要求

解题思路

来自[负雪明烛]
题目有个明显的提示:求组合的个数,而不是每个组合。如果是要求出每个组合,那么必须使用回溯法,保存所有路径。但是如果是组合个数,一般都应该想到[动态规划]的解法。
直接写出[动态规划]的解法,是有一定难度的。不妨先写出[记忆化递归],然后进行修改[动态规划]。

方法一:递归

要求构成target有多少种组合方法,这里的变量应该是target,所以,令函数dp(x)表示从nums中挑选数字可以构成x的方法数(递归最基本的就是理解这个定义!)。最终返回的应该是dp(target)
对于题目输入nums=[1,2,3],target =4的时候:要求有多少种方法能够组成4,即要求dp[4]。思考过程如下:
我们遍历nums,判断如果构成target的时候,选择了nums[i],那么剩余的target-nums[i]仍在nums中选择的话,会有多少种方法。
于是一步一步出现了递归。这就是将大问题拆成小问题,然后发现小问题恰好可以用同样的函数解决,这就是递归思想。递归是一种思想与现象,绝不是为了递归而递归。
那么递归终止条件是什么呢?也就是说最基础的case应该直接返回什么结果?

  • 如果给出的数字都是正整数,因此如果当要求的target<0的时候,无论如何都无法从数组中挑选元素构成,所以应该返回0;
  • 当要求的target==0 的时候,需要return 1。为什么?因为我们注意题目给出的输入target一定是大于0的,如果在递归的时候target==0,说明在for循环中的target-num得到了0,表示nums数组中乔安后有一个数字等于target。所以需要返回1。
    会超时。
    时间复杂度: O ( N t r a g e t ) O(N^{traget}) O(Ntraget),N是nums的长度,每次递归需要计算N次,递归深度最多target。
    空间复杂度: O ( t a r g e t ) O(target) O(target)

方法二:记忆化递归

上面递归方法会超时,是因为有重复计算,比如计算dp(4)的时候,计算了dp(2),而计算dp(3)的时候又再次计算了dp(2)。如果我们在递归的过程中,把已经计算了的结果放在数组、字典中保存,那么下次需要再计算相同的值的时候,直接从数组/字典中调用相同的计算结果,就能省下很多计算。
下面的代码演示了如何使用[记忆化递归]。定义了一个dp数组,保存已经计算量的每个dp(x)dp数组的每个位置初始化为-1,表示还没计算过。在递归函数刚开始的时候,不仅要判断target是否<0,还要判断当前计算的target是否计算过(即dp[target] !=-1)。只有在没计算过的情况下,才执行递归。并且在执行递归之后,需要把当前target的计算结果保存到dp数组中。

代码:
class Solution(object):
    def combinationSum4(self, nums, target):
        self.dp = [-1] * (target + 1)
        self.dp[0] = 1
        return self.dfs(nums, target)

    def dfs(self, nums, target):
        if target < 0: return 0
        if self.dp[target] != -1:
            return self.dp[target]
        res = 0
        for num in nums:
            res += self.dfs(nums, target - num)
        self.dp[target] = res
        return res
复杂度分析

时间复杂度: O ( N ∗ t a r g e t ) O(N * target) O(Ntarget)
空间复杂度: O ( t a r g e t ) O(target) O(target)

方法三:动态规划

理解了[记忆化递归]之后,离写出动态规划只有一步之遥。递归是自顶向下的计算方式(大问题-》小问题),而动态规划是自底向上的计算方式(小问题-》大问题)
动态规划也同样地定义dp数组,dp[i]表示从nums中抽取元素组成target的方案数。dp数组的长度是target+1。其中dp[0]表示从数组中抽取任何元素组成0的方案数,根据我们在递归时的分析,我们需要知道令dp[0] = 1。其他位置的dp[i]需要初始化为0,表示我们还没有计算过这个位置,默认的方案数为0。
想要计算得到target,需要把dp[1~target]的各个元素都计算出来。每个位置的计算都是为了后面的计算做准备。

代码:
class Solution(object):
    def combinationSum4(self, nums, target):
        dp = [0] * (target + 1)
        dp[0] = 1
        res = 0
        for i in range(target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
        return dp[target]

复杂度分析:

时间复杂度: O ( N ∗ t a r g e t ) O(N * target) O(Ntarget)
空间复杂度: O ( t a r g e t ) O(target) O(target)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/295808.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Maven 开发环境搭建

Maven介绍 Apahche 软件基金会&#xff08;非营业的组织&#xff0c;把一些开源软件维护管理起来&#xff09; maven apahce的一个开宇拿项目&#xff0c;是一个优秀的项目构建&#xff08;管理工具&#xff09; maven 管理项目的jar 以及jar与jar之间的依赖 maven 可以完成…

前端结合MQTT实现连接 订阅发送信息等操作 VUE3

MQTT客户端下载 使用测试 在我之前文章中 MQTT下载基础使用 下面记录一下前端使用的话的操作 1.安装 npm i mqtt引入 import * as mqtt from "mqtt/dist/mqtt.min"; //VUE3 import mqtt from mqtt //VUE2 一、MQTT协议中的方法 Connect。等待与服务器建立连接…

04set注入专题/简单类型/数组/List/Set/Map/空字符串/null/特殊符号

1.1注入外部Bean 在之前使用的案例就是注入外部Bean的方式。 <!-- class属性声明要管理哪个类中的对象 property标签的name是提示set方法名ref标签指明注入的bean的id--><bean id"userServiceBean" class"com.powernode.spring6.service.UserService…

leetcode:908. 最小差值 I

一、题目 二、函数原型 int smallestRangeI(int* nums, int numsSize, int k) 三、思路 本题题目有些绕口&#xff0c;但是无伤大雅。本质就是可以对数组中的每个元素进行加/减 k 的操作&#xff0c;然后求数组中的最大、最小元素的最小差值。 分为几种情况&#xff1a; …

C 语言编程软件 | Dev-C++ 的安装及使用

Hi&#xff0c;大家好&#xff0c;我是源于花海。本文主要了解 Dev-C 的安装及使用。Dev-C&#xff08;又称Dev-Cpp&#xff09;是Windows环境下的一个轻量级 C/C集成开发环境&#xff08;IDE&#xff09;。它集合了功能强大的源码编辑器、MingW64/TDM-GCC 编译器、GDB 调试器和…

【数据库原理】(10)数据定义功能

SQL 数据定义功能包括定义模式、定义表、定义索引和定义视图,其语句如表所示。 一.创建、删除模式 1.创建模式 (Create Schema) 用途&#xff1a;创建模式是为了在数据库中定义一个新的命名空间&#xff0c;它可以包含多个数据库对象。 语法&#xff1a; CREATE SCHEMA &…

万界星空科技MES系统中的设备管理模块

随时工厂数字化建设的大力推进&#xff0c;设备管理的效率得到了很大的提升&#xff0c;特别是作为机加工企业&#xff0c;设备是整个企业非常重要的核心资产。 MES系统主要包含了生产计划、生产过程管理、质量管理、物料管理、设备维护等多个模块&#xff0c;各个模块之间相互…

深度学习中的自动化标签转换:对数据集所有标签做映射转换

在机器学习中&#xff0c;特别是在涉及图像识别或分类的项目中&#xff0c;标签数据的组织和准确性至关重要。本文探讨了一个旨在高效转换标签数据的 Python 脚本。该脚本在需要更新或更改类标签的场景中特别有用&#xff0c;这是正在进行的机器学习项目中的常见任务。我们将逐…

safari缓存清理

safari缓存清理 点击顶端Safari浏览器–>点击偏好设置 点击隐私–>管理网站数据 全部移除

数据库初始化脚本(用 truncate 命令一键清空某个数据库中全部数据表数据)

数据库初始化脚本&#xff08;用 truncate 命令一键清空某个数据库中全部数据表数据&#xff09; 1.执行下面的sql语句生成“清空数据库的sql脚本”2.执行“清空数据库的sql脚本” 在开发中&#xff0c;当数据表结构有变动或者数据库中有脏数据时&#xff0c;想要清空数据表中的…

深度学习(Pytorch版本)

零.前置说明 1、code 2、视频 数据预处理实现_哔哩哔哩_bilibili

探讨一下WebINFO 下的一些思考

在平时的开发中&#xff0c;我们经常看到一个/WEB-INF 这个目录&#xff0c;这个是web 容器初始化加载的一个标准路径。官方解释&#xff1a;WEB-INF 是 Java 的 web 应用的安全目录。所谓安全就是客户端无法访问&#xff0c;只有服务端可以访问的目录。也就是说&#xff0c;这…

Unity游戏内相机(主角头部视角)的旋转问题:“万向节锁定”(Gimbal Lock)

前言&#xff1a; 在Unity中&#xff0c;相机的正前方是Z正半轴&#xff0c;相机的正右方是X正半轴&#xff0c;相机的正上方是Y正半轴。这个很好理解。 现在&#xff0c;我想要相机看向左前上方45&#xff0c;你会觉得要怎么做呢&#xff1f; 如果是我的话&#xff0c;我的第一…

鹿目标检测数据集VOC格式500张

鹿&#xff0c;一种优雅而神秘的哺乳动物&#xff0c;以其优美的外形和独特的生态习性而备受人们的喜爱。 鹿的体型通常中等&#xff0c;四肢细长&#xff0c;身体线条流畅。它们的头部较小&#xff0c;耳朵大而直立&#xff0c;眼睛明亮有神。鹿的毛色因品种而异&#xff0c;…

RocketMQ MQClientInstance、生产者实例启动源码分析

&#x1f52d; 嗨&#xff0c;您好 &#x1f44b; 我是 vnjohn&#xff0c;在互联网企业担任 Java 开发&#xff0c;CSDN 优质创作者 &#x1f4d6; 推荐专栏&#xff1a;Spring、MySQL、Nacos、Java&#xff0c;后续其他专栏会持续优化更新迭代 &#x1f332;文章所在专栏&…

第11章 GUI Page462~476 步骤二十三 步骤二十四 Undo/Redo ①为Undo/Redo做准备工作,弹出日志窗口

step23和step24合起来学习 工程一 1.主窗口类中添加新的私有成员数据&#xff1a; 2 主窗口构造函数中&#xff0c;最后一行加入&#xff0c;用于调试的Log功能 3 鼠标弹起函数&#xff0c;添加Undo动作 4 编译之后报错&#xff1a;ActionLink不是一个类型 5 新增一个头文件…

2024年自动化测试面试题分享(含答案)

1、你做了几年的测试、自动化测试&#xff0c;说一下 selenium 的原理是什么&#xff1f; 我做了五年的测试&#xff0c;1年的自动化测试&#xff1b; selenium 它是用 http 协议来连接 webdriver &#xff0c;客户端可以使用 Java 或者 Python 各种编程语言来实现&#xff1…

20240105移远的4G模块EC20在Ubuntu 20.04.6 LTS下使用联通5G卡上网的步骤

20240105移远的4G模块EC20在Ubuntu 20.04.6 LTS下使用联通5G卡上网的步骤 2024/1/5 10:11 缘起&#xff1a;需要在Firefly的AIO-3399J开发板上调试移远的4G模块EC20&#xff08;Android10/11/12&#xff09;&#xff0c;需要现在先测试EC20的好坏&#xff01; 陶老板告诉我找一…

书生浦语大模型训练营第一课笔记:全链路开源体系

AI 的研究方向&#xff0c;从专业模型转变为通用模型。 上海人工智能实验室的开源历程 覆盖了轻量级、中量级、重量级的模型&#xff1b; 7B 20B 都是免费开源的&#xff0c;可商用。 从模型到应用 开源了全链路工具。 ![

Linux第20步_在虚拟机上安装“Visual Studio Code”

1、双击windows系统桌面上的“FileZilla Client.exe”&#xff0c;打开FTP客户端&#xff0c;点击03软件下的Visual Studio Code&#xff0c;发现code_1.50.1-1602600906_amd64。 2、点击“文件”&#xff0c;然后点击“站点管理器”&#xff0c;见下图操作&#xff1a; 3、点…