动态规划专练( 337.组合总和Ⅳ)

337.组合总和Ⅳ

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

提示:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

题解:

本题相较于518.零钱兑换Ⅱ有很相似的地方,都是完全背包的应用场景,区别在于,518题是求解的组合数,而本题求解的是序列数。

具体的思路这里就不说了,可以去别的地方找详解,说一下我这个题踩到的坑(仅限菜鸡)。

由于滚动数组的逻辑写起来让我感觉混乱,因此我的写法还是喜欢停留在使用二维dp来求解。然后组合数和序列数这两种情况,虽然有点难以理解,但是记忆了对应的代码写法,无非是两个for循环的位置换一下。

  • 组合数:先遍历物品,再遍历背包容量
  • 序列数:先遍历背包容量,再遍历物品

因此我很快的写出了下面的代码(错的)

package com.offer;

import com.offer.leetcode.datastruct.DPUtils;

/**
 * @author bwzfy
 * @create 2024/4/14
 **/
public class _377组合总和Ⅳ {

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

    public static int combinationSum4(int[] nums, int target) {
        int[][] dp = new int[nums.length + 1][target + 1];
        dp[0][0] = 1;
        for (int i = 1; i < nums.length + 1; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; j < target + 1; j++) {
            for (int i = 1; i < nums.length + 1; i++) {
                if (nums[i - 1] <= j) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        DPUtils.printDP(dp);
        return dp[nums.length][target];
    }

}

由于前面练习的背包题,因此这个题写的很流畅,运行测试用例的时候还是很自信的,结果没过。。。。

打印出来的dp如下:

思来想去没想明白,然后再使用518题的代码来运行了一下,打印出了二维数组,发现在使用二维数组的情况下,两个for循环的位置是不重要的,他们求的都是组合数(裂开)。

因此后来改了滚动数组的写法,得到了正确的结果,代码如下。

package com.offer;

import com.offer.leetcode.datastruct.DPUtils;

/**
 * @author bwzfy
 * @create 2024/4/14
 **/
public class _377组合总和Ⅳ {

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

    public static int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int j = 1; j < target + 1; j++) {
            for (int i = 1; i < nums.length + 1; i++) {
                if (nums[i - 1] <= j) {
                    dp[j] = dp[j] + dp[j - nums[i - 1]];
                }
            }
        }
        DPUtils.printDP(dp);
        return dp[target];
    }

}

总结得到的结果就是,双重for循环的位置的意义仅对于滚动数组有效,以后再遇到这种完全背包的求个数问题,需要使用滚动数组来写

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

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

相关文章

2022年蓝桥杯省赛软件类C/C++B组----积木画

想借着这一个题回顾一下动态规划问题的基本解法&#xff0c;让解题方法清晰有条理&#xff0c;希望更多的人可以更轻松的理解动态规划&#xff01; 目录 【题目】 【本题解题思路】 【DP模版】 总体方针&#xff1a; 具体解题时的套路&#xff1a; 【题目】 【本题解题思…

Python判断节假日的几种方式,你学废了吗?

最近在推进信息安全巡检的工作&#xff0c;按公司制度要求和信息安全标准&#xff0c;要求按时对硬件设备、网络、机房、应用系统、数据库等等做巡检工作。为了保证达到信息安全的目标&#xff0c;要求在每周四和节假日的前一天对各类设备和系统进行巡检。 1、使用holidays库判…

zookeeper分布式应用程序协调服务+消息中间件kafka分布式数据处理平台

一、zookeeper基本介绍 1.1 zookeeper的概念 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件&#xff0c;提供的功能包括&#xff1a;配置维护、域名服务、…

python小游戏

这些游戏你玩过几个&#xff1f; 1.贪吃蛇2.吃豆人3.加农炮4.四子棋5. Fly Bird<font color #f3704ab>6.记忆&#xff1a;数字对拼图游戏&#xff08;欢迎挑战&#xff01;用时&#xff1a;2min&#xff09;7.乒乓球8.上课划水必备-井字游戏&#xff08;我敢说100%的人都…

代码随想录算法训练营第二十七天|39.组合总和、40.组合总和II、131.分割回文串

39.组合总和 思路&#xff1a; 本题和77.组合 &#xff0c;216.组合总和III的区别是&#xff1a;本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本题搜索的过程抽象成树形结构如下&#xff1a; 注意图中叶…

《HF经理》:二认知误区

一、管理者掌握重要权力&#xff1a; 二、全力来自管理者的职位&#xff1a; 三、管理者必须控制自己的直接下属&#xff1a; 对策&#xff1a;展示自己的品质&#xff0c;能力和影响力 四、管理者必须建立良好的个人关系&#xff1a; 五、管理这必须确保一切运行正常&…

【爬虫开发】爬虫从0到1全知识md笔记第5篇:Selenium课程概要,selenium的其它使用方法【附代码文档】

爬虫开发从0到1全知识教程完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;爬虫课程概要&#xff0c;爬虫基础爬虫概述,,http协议复习。requests模块&#xff0c;requests模块1. requests模块介绍,2. response响应对象,3. requests模块发送请求,4. request…

分享2024 golang学习路线

写在前面 Go语言&#xff08;也称为Golang&#xff09;是Google开发的一种静态强类型、编译型语言&#xff0c;它具有简洁、快速、安全、并发等特点&#xff0c;尤其适合构建大型软件、微服务架构和云平台服务。Go的学习曲线相对平缓&#xff0c;社区活跃&#xff0c;是现代编…

韩顺平 | 零基础快速学Python(16) 文件处理

文件 输入与输出 输入&#xff1a;数据从数据源(文件)到程序(内存)&#xff1b; 输出&#xff1a;数据从程序(内存)到数据源(文件)。 #mermaid-svg-06PG6JZq4jJMV1oH {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-sv…

五、LoadBalancer负载均衡服务调用

一、Ribbon目前也进入维护模式 1、是什么 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的工具。 简单的说&#xff0c;Ribbon是Netflix发布的开源项目&#xff0c;主要功能是提供客户端的软件负载均衡算法和服务调用。Ribbon客户端组件提供一系列完善的…

掌握CRM+邮箱技巧:销售速度与客户信任双丰收

在千行百业都在谈提效的今天&#xff0c;如果您的销售团队效率较低&#xff0c;恐怕很难过好2024。销售团队提效是个大话题&#xff0c;总的说来就是销售团队需要在正确的时间做正确的事。如何做到&#xff1f;自然要借助CRM工具。过去我们也讲了不少CRM如何辅助销售团队提效的…

Playwright已经是目前最好的测试自动化工具了吗?

作者观点&#xff1a;很长时间以来&#xff0c;Selenium是QA工程师寻求测试自动化解决方案的首选测试框架。它能够测试任何浏览器&#xff08;这在IE浏览器的统治时期尤其重要&#xff09;和任何平台。然而&#xff0c;现在看来&#xff0c;那个时代已经过去了。 今天&#xf…

Python机器学习实战教程

一、引言 机器学习是人工智能的一个子集&#xff0c;它使用算法来让计算机系统从数据中“学习”并改进其性能&#xff0c;而无需进行明确的编程。Python因其易于学习、强大的库和广泛的应用场景&#xff0c;成为了机器学习的首选语言。本教程旨在帮助读者从零开始学习Python机…

APP开发突增20倍!安卓和鸿蒙你站哪边?

随着科技的快速发展&#xff0c;智能设备已经成为我们生活中不可或缺的一部分。 根据不少业内人士爆料&#xff0c;今年9月华为将发布mate70系列&#xff0c;而同时华为自己也官宣了"鸿蒙星河版"&#xff0c;也就是原生鸿蒙系统&#xff0c;将于今年4季度商用。这很…

31、链表-K个一组反转链表

思路&#xff1a; 首先知道如何反转链表&#xff0c;其次找出每组的开始节点和结束节点&#xff0c;然后对于不足与k个的链表保持原状。 代码如下&#xff1a; class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (headnull||k1){return head;}ListN…

家居网购项目(Ajax验证用户名+上传图片)

文章目录 1.Ajax验证用户名1.程序框架图2.修改MemberServlet3.修改login.jsp4.结果展示 2.Ajax判断验证码是否输入正确1.修改MemberServlet2.修改login.jsp3.结果展示 3.Ajax添加购物车1.程序框架图2.修改CartServlet2.修改index.jsp3.解决问题—未登录直接添加购物车&#xff…

每日一题---OJ题: 有效的括号

片头 嗨! 小伙伴们,大家好! 我们又见面啦! 今天我们来一起尝试一下这道题目---有效的括号,准备好了吗? 我们开始咯! 说实话,我刚开始做这道题的时候也是一脸懵,怎么进行括号匹配呢? 别慌,我们一起画个图,分析分析括号匹配的过程~ 如下图所示,上方表示一个字符串数组,存放不…

【C++】力扣OJ题:找出只出现一次的数字

Hello everybody!这是我第一次写关于OJ题目的博客&#xff0c;因为正好学到完了C的STL库&#xff0c;就顺手刷了一些OJ题。 我今天要介绍的题目虽然是力扣上的简单题&#xff0c;但思想很巧妙&#xff0c;我觉得有必要和大家分享一下&#xff01; 1.题目 2.代码 class Solut…

【Go】原子并发操作

目录 一、基本概念 支持的数据类型 主要函数 使用场景 二、基础代码实例 开协程给原子变量做加法 统计多个变量 原子标志判断 三、并发日志记录器 四、并发计数器与性能监控 五、优雅的停止并发任务 worker函数 Main函数 应用价值 Go语言中&#xff0c;原子并发操…

飞机飞行数据三维可视化管控系统更智能、精准

近年来&#xff0c;随着无人化工厂和智能工厂在中国大量涌现&#xff0c;基于成熟的数字孪生理念&#xff0c;智能工厂三维可视化虚拟管控系统引领未来工业革命的先锋。数字孪生公司深圳华锐视点结合前沿的三维仿真、GIS和三维可视化技术技术&#xff0c;深度集成工厂生产、经营…