算法学习——LeetCode力扣动态规划篇4

算法学习——LeetCode力扣动态规划篇4

在这里插入图片描述

377. 组合总和 Ⅳ

377. 组合总和 Ⅳ - 力扣(LeetCode)

描述

给你一个由 不同 整数组成的数组 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零钱兑换II 的区别是

  • 518零钱兑换II 是组合数,有多少种组合
  • 此题是找排序数

如果求组合数就是外层for循环遍历物品,内层for遍历背包。

如果求排列数就是外层for遍历背包,内层for循环遍历物品。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
       vector<int> dp(target+1 ,0);

       dp[0] = 1;
        for(int j=0 ; j<=target ;j++)
        {
            for(int i=0 ; i<nums.size() ;i++)
            {
                if(j>=nums[i] && dp[j] < INT_MAX - dp[j-nums[i]])
                {
                  dp[j] += dp[j-nums[i]];
                } 
                else dp[j] = dp[j];
            }
        }
       return dp[target];
    }
};

C++测试用例有两个数相加超过int的数据,所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。

322. 零钱兑换

322. 零钱兑换 - 力扣(LeetCode)

描述

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

示例

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3
输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0

提示

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

代码解析

动态规划

dp[j]:凑足总额为j所需钱币的最少个数为dp[j]

得到dp[j],只有一个来源,dp[j - coins[i]]。

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]

递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

首先凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1 ,INT_MAX);
       
        dp[0]=0;
        
        for(int i=0 ; i<coins.size() ; i++)
        {
            for(int j=0 ; j<=amount  ;j++)
            {
                if(j>=coins[i] && dp[j-coins[i]] != INT_MAX)
                {
                    dp[j] = min( dp[j], dp[j-coins[i]] + 1);
                }
            }
        }

        if(dp[amount]==INT_MAX) return -1;

        return dp[amount];
    }
};

279. 完全平方数

279. 完全平方数 - 力扣(LeetCode)

描述

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。

示例

示例 1:

输入:n = 12
输出:3
解释:12 = 4 + 4 + 4

示例 2:

输入:n = 13
输出:2
解释:13 = 4 + 9

提示

1 <= n <= 104

代码解析

动态规划

和322零钱兑换完全一致

自己构建完全平方数组,作为价格数组
找到刚好装满背包,但使用金币数量最少的金币数

class Solution {
public:
    int numSquares(int n) {
        vector<int> sqrt_num;
        vector<int> dp(n+1,INT_MAX);
        int tmp = 1;
        while( pow(tmp,2) <= n )
        {
            sqrt_num.push_back(pow(tmp,2));
            tmp++;
        }
        dp[0]=0;
        for(int i=0 ;i<sqrt_num.size();i++)
        {
            for(int j=sqrt_num[i] ; j<=n ;j++)
                dp[j] = min(dp[j] , dp[j-sqrt_num[i]]+1 );
        }
        
        return dp[n];
    }
};

139. 单词拆分

139. 单词拆分 - 力扣(LeetCode)

描述

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例

示例 1:

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2:

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意,你可以重复使用字典中的单词。

示例 3:

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

提示

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同

代码解析

动态规划

单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词,说明就是一个完全背包!

dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

dp[j]=true 来自于 dp[i]=true + 字串s(i,j-i)可以在字典中找到。
例如输入“leetcode” ,dp[ 0 ] 初始化为1 ,
dp[ 4 ] = 1 , 因为 dp[ 0 ] =1 ,字串 s( 0 , 4 - 0)即”leet“ 可以在字典找到
dp[ 8 ] = 1 , 因为 dp[ 4 ] =1 ,字串 s( 4 , 8 - 4)即”code“ 可以在字典找到

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1 ,false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        
        dp[0] = true;
        // dp[j]=true 来自于 dp[i]=true + 字串s(i,j-i)可以在字典中找到。
        for(int j = 1 ; j<=s.size() ; j++)//背包尺寸
        {
            for(int i = 0 ; i < j ;i++ )//字串长度
            {
                string word = s.substr( i , j-i );
                if(wordSet.find(word) != wordSet.end() && dp[i]==true )
                    dp[j] = true;
            }  
        }
        // for(auto it:dp) cout<<it<<' ';
        return dp[s.size()];
    }
};

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

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

相关文章

JSQLParserException异常

前言 SQL中加入了租户字段&#xff0c;报这个错&#xff0c;可以查出数据&#xff0c;但是不多&#xff1b;SQL检查无问题 解决 原因一 引入新的SQL解析器检查解析SQL&#xff0c;与mybatis多租户无关 参考 <!--jsqlparser版本太低也无法解析&#xff0c;如2.0--> &…

左侧或水平导航菜单栏与main区域联动

系列文章目录 一、elementui 导航菜单栏和Breadcrumb 面包屑关联 二、左侧导航菜单栏与main区域联动 文章目录 系列文章目录前言一、实现步骤1.<el-menu>中设置属性router为true2.<el-menu-item>中设置路由 route"/"3.<el-main>里设置路由出口4…

Android Studio Iguana | 2023.2.1 补丁 1

Android Studio Iguana | 2023.2.1 Canary 3 已修复的问题Android Gradle 插件 问题 295205663 将 AGP 从 8.0.2 更新到 8.1.0 后&#xff0c;任务“:app:mergeReleaseClasses”执行失败 问题 298008231 [Gradle 8.4][升级] 由于使用 kotlin gradle 插件中已废弃的功能&#…

游戏行业行业竞争越来越激烈,遇到DDoS攻击遭受严重损失该如何解决

近年来&#xff0c;我们见证了数字化的快速发展&#xff0c;随着这样的发展&#xff0c;网络的威胁也逐渐增多&#xff0c;在网络攻击门槛不断降低&#xff0c;行业竞争越来越激烈&#xff0c;游戏行业的DDoS攻击如雨点般密集&#xff0c;在整个DDoS攻击的份额中&#xff0c;游…

C语言goto语句介绍

在C语言中&#xff0c;goto语句是一种流程控制语句&#xff0c;用于无条件地转移到程序中的特定标签位置。尽管goto语句在编程中具有一定的争议&#xff0c;但在某些情况下&#xff0c;它可以提供一种简单有效的解决方案。本文将深入介绍C语言中的goto语句&#xff0c;包括其基…

android安卓英语学习课设

一、关于这个项目ELAPP 该项目是一个基于java开发的服务器-客户端模式的安卓英语学习软件&#xff0c;主要功能点就是背单词&#xff0c;中英文翻译&#xff0c;OCR文字翻译。 服务器端使用springboot&#xff0c;mybatisplus&#xff0c;MySQL&#xff0c;mongodb&#xff0…

Solo 开发者周刊 (第9期):Dawwin首位人工智能编程师或将改变未来?

这里会整合 Solo 社区每周推广内容、产品模块或活动投稿&#xff0c;每周五发布。在这期周刊中&#xff0c;我们将深入探讨开源软件产品的开发旅程&#xff0c;分享来自一线独立开发者的经验和见解。本杂志开源&#xff0c;欢迎投稿。 好文推荐 Dawwin首位人工智能编程师&#…

企业数据被新型.rmallox勒索病毒加密,应该如何还原?

.rmallox勒索病毒为什么难以解密&#xff1f; .rmallox勒索病毒难以解密的主要原因在于其采用了高强度的加密算法&#xff0c;并且这些算法被有效地实施在了病毒程序中。具体来说&#xff0c;.rmallox勒索病毒使用了RSA和AES这两种非常成熟的加密算法。RSA是一种非对称加密算法…

linux安装Tomcat

linux安装Tomcat 下载地址&#xff1a;https://archive.apache.org/dist/tomcat/tomcat-8/v8.5.87/bin/apache-tomcat-8.5.87.tar.gz 将下载的安装包传到该文件夹 解压安装包 tar -zxvf apache-tomcat-8.5.87.tar.gz 配置环境变量 vim /etc/profile 添加指定文件最下方 expo…

【编程笔记】学会使用 Git

目录 一、介绍 Git二、安装 Git三、 常用 linux 目录四、Git 的必要配置(1) 查看和删除之前的配置(2) 配置 Git 五、Git 基本理论六、Git 项目搭建七、Git 文件操作八、分支Git 笔记 ❀❀❀(1) 常规使用(2) 分支 一、介绍 Git &#x1f4d6; VCS&#xff1a;Version Control S…

第六讲 B+树索引

1 B树大家庭 有一种称为 B 树的特定数据结构&#xff0c;人们还使用该术语来泛指一类平衡树数据结构&#xff1a; B-Tree (1971)BTree (1973)B*Tree (1977?)B link-Tree (1981)Bε-Tree (2003)Bw-Tree (2013) 2 B树 BTree 是一种自平衡【self-balance】、有序【ordered】的…

JavaEE 初阶篇-深入了解多线程安全问题(出现线程不安全的原因与解决线程不安全的方法)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 多线程安全问题概述 1.1 线程不安全的实际例子 2.0 出现线程不安全的原因 2.1 线程在系统中是随机调度且抢占式执行的模式 2.2 多个线程同时修改同一个变量 2.3 线…

C语言-编译和链接

目录 1.前言2.编译2.1预处理&#xff08;预编译&#xff09;2.1.1 #define 定义常量2.1.2 #define 定义宏2.1.3带有副作用的宏参数2.1.4宏替换规则2.1.5 #和##2.1.5.1 #运算符2.1.5.2 ## 运算符 2.1.6 命名约定2.1.7 #undef2.1.8 条件编译2.1.9 头文件的包含2.1.9.1 本地文件包…

基于RIP的MGRE综合实验

实验拓扑&#xff1a; 实验要求&#xff1a; 1、R5为ISP&#xff0c;只能进行IP地址配置&#xff0c;其所有地址均配为公有Ip地址; 2、R1和R5间使用PPP的PAP认证&#xff0c;R5为主认证方&#xff1b; R2与R5之间使用ppp的cHAP认证&#xff0c;R5为主认证方; R3与R5之间使用H…

Clip算法解读

论文地址&#xff1a;https://arxiv.org/pdf/2103.00020.pdf 代码地址&#xff1a;https://github.com/OpenAI/CLIPz 中文clip代码&#xff1a;https://gitcode.com/OFA-Sys/Chinese-CLIP/overview 一、动机 主要解决的问题&#xff1a; 超大规模的文本集合训练出的 NLP 模…

pbrt-v4 windows编译失败指南

cpu下编译成功很容易&#xff0c;但是gpu有点麻烦&#xff0c;主要有下面几个坑 安装optix 7&#xff0c;cmake build 要加上PBRT_OPTIX_PATH cmake cuda 版本要对应&#xff0c;不然会出现 cuda not found&#xff0c;或者generate的时候报错&#xff0c;导致最后pbrt.exe --…

FANUC机器人故障诊断—报警代码更新(三)

FANUC机器人故障诊断中&#xff0c;有些报警代码&#xff0c;继续更新如下。 一、报警代码&#xff08;SRVO-348&#xff09; SRVO-348DCS MCC关闭报警a&#xff0c;b [原因]向电磁接触器发出了关闭指令&#xff0c;而电磁接触器尚未关闭。 [对策] 1.当急停单元上连接了CRMA…

在react项目用echarts绘制中国地图

文章目录 一、引入echarts二、下载地图json数据三、编写react组件四、组件使用 一、引入echarts 安装&#xff1a;npm i echarts --save 二、下载地图json数据 由于echarts内部不再支持地图数据&#xff0c;所以要绘制地图需要自己去下载数据。建议使用阿里云的。 地址&…

接口自动化框架搭建(四):pytest的使用

1&#xff0c;使用说明 网上资料比较多&#xff0c;我这边就简单写下 1&#xff0c;目录结构 2&#xff0c;test_1.py创建两条测试用例 def test_1():print(test1)def test_2():print(test2)3&#xff0c;在pycharm中执行 4&#xff0c;执行结果&#xff1a; 2&#xff0…