算法学习——LeetCode力扣动态规划篇3(494. 目标和、474. 一和零、518. 零钱兑换 II)

本文主要是介绍算法学习——LeetCode力扣动态规划篇3(494. 目标和、474. 一和零、518. 零钱兑换 II),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

在这里插入图片描述

494. 目标和

494. 目标和 - 力扣(LeetCode)

描述

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个 表达式 :

例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例

示例 1:

输入:nums = [1,1,1,1,1], target = 3
输出:5
解释:一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2:

输入:nums = [1], target = 1
输出:1

提示

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

代码解析

这道题根本还是回到了在数组中找到一个集合,使得该集合与其余部分之差为target,通过公式推导:
我们可以知道 该集合的值为:(sum-target)/2;

回溯法

目的是找到和为**(sum-target)/2** 的种类

class Solution {
public:int result = 0;void backtracking(vector<int>& nums, int target ,int deep ,int sum){if(sum > target)return;if(sum == target)result++;if(deep == nums.size()) return;//从任一点开始for(int i= deep ; i < nums.size() ;i++){backtracking(nums,target , i+1  , sum + nums[i]);}return;}int findTargetSumWays(vector<int>& nums, int target) {int sum = 0 , diff = 0;for(auto it:nums) sum += it;diff = sum - target;if( diff<0 || diff%2==1 ) return 0;//回溯找diff/2backtracking(nums,diff/2,0 ,0);return result;}
};
动态规划
  1. 背包定义: dp[i][j] , i是使用0-i的元素,j是背包容量,dp[i][j]是使用这么多个元素恰好凑成j的情况
  2. 初始化:dp[0][0]为1,装满容量为0的背包,有一种方法。dp[0][j],看第一个元素的大小情况,进行赋值1(如果第一个元素为0.则dp[0][0]应该为2),其他层的根据第一层改变.
  3. 遍历顺序:从上往下
  4. 递推公式: dp[i][j]=dp[i-1][j](不需要num[i]就能够凑出j的情况)+dp[i-1][j-nums[i]];(需要num[i]凑出j空间的情况) 最终就能实现,从0-i元素当中组合,得到target的所有情况。
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0 , diff = 0;for(auto it:nums) sum += it;diff = sum - target;if( diff<0 || diff%2==1 ) return 0;vector<vector<int>>  dp( nums.size() , vector<int>(diff/2 + 1 , 0) ) ;dp[0][0] = 1;for(int j=0 ; j<(diff)/2+1 ; j++)if(j==nums[0]) dp[0][j] += 1;for(int i=1 ; i<nums.size() ;i++){for(int j=0 ; j<(diff)/2+1 ; j++){if(j>=nums[i])dp[i][j] = dp[i-1][j] + dp[i-1][ j - nums[i]] ;elsedp[i][j] = dp[i-1][j];}}      return dp[nums.size()-1][(diff)/2];}
};

474. 一和零

474. 一和零 - 力扣(LeetCode)

描述

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度,该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素,集合 x 是集合 y 的 子集 。

示例

示例 1:

输入:strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出:4
解释:最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ,因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意,因为它含 4 个 1 ,大于 n 的值 3 。

示例 2:

输入:strs = [“10”, “0”, “1”], m = 1, n = 1
输出:2
解释:最大的子集是 {“0”, “1”} ,所以答案是 2 。

提示

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 ‘0’ 和 ‘1’ 组成
1 <= m, n <= 100

代码解析

动态规划(01背包,三级数组)

和经典的背包问题只有一种容量不同,这道题有两种容量,即选取的字符串子集中的 0 和 1 的数量上限。

经典的背包问题可以使用二维动态规划求解,两个维度分别是物品和容量。这道题有两种容量,因此需要使用三维动态规划求解,三个维度分别是字符串、0的容量和 1 的容量。

定义三维数组dp,其中dp[i][j][k] 表示在前 i 个字符串中,使用 j 个 0 和 k 个 1 的情况下最多可以得到的字符串数量。
当 0 和 1 的容量分别是 j 和 k 时,考虑以下两种情况:

  • 如果 j< zeros 或 k<ones,则不能选第 i 个字符串,此时有 dp[i][j][k] = dp[i−1][j][k];

  • 如果 j ≥ zeros 且 k ≥ones,则如果不选第 i个字符串,有dp[i][j][k]=dp[i−1][j][k],如果选第 i个字符串,有 dp[i][j][k]=dp[i−1][j−zeros][k−ones]+1,dp[i][j][k] 的值应取上面两项中的最大值。

因此状态转移方程如下:
在这里插入图片描述

class Solution {
public:int find_0(string s1){int num = 0;for(auto it:s1) if(it == '0') num++;return num;}int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<vector<int>>>  dp( strs.size() ,vector<vector<int>>( m+1 ,vector<int>( n+1,0) ));int num_0 = 0,num_1 = 0;num_0 = find_0(strs[0]);num_1 = strs[0].size() - num_0;for(int j=0 ; j<= m ;j++){for(int k=0 ; k<= n ;k++){if( j>= num_0 && k>= num_1)dp[0][j][k] = 1;}}for(int i=1 ; i<strs.size() ; i++){num_0 = find_0(strs[i]);num_1 = strs[i].size() - num_0;for(int j=0 ; j<=m ;j++){ for(int k=0 ; k<=n ;k++){if( j>= num_0 && k>= num_1)dp[i][j][k] = max( dp[i-1][j][k], dp[i-1][j - num_0][k - num_1] + 1);elsedp[i][j][k] = dp[i-1][j][k];}}}int max_num = 0;for(int i=0 ; i<strs.size() ; i++){if(dp[i][m][n] > max_num) max_num = dp[i][m][n];// cout<<dp[i][m][n]<<' ';}return max_num ;}
};
动态规划(滑动数组,二级数组)

由于dp[i][][] 的每个元素值的计算只和dp[i−1][][] 的元素值有关,因此可以使用滚动数组的方式,去掉 dp 的第一个维度,将空间复杂度优化到 O(mn)O(mn)。

实现时,内层循环需采用倒序遍历的方式,这种方式保证转移来的是 dp[i−1][][] 中的元素值。

class Solution {
public:int find_0(string s1){int num = 0;for(auto it:s1) if(it == '0') num++;return num;}int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>>  dp( m+1 ,vector<int>(n+1,0));int num_0 = 0,num_1 = 0;for(int i=0 ; i<strs.size() ; i++){num_0 = find_0(strs[i]);num_1 = strs[i].size() - num_0;for(int j=m ; j>=num_0;j--){ for(int k=n ; k>=num_1 ;k--){dp[j][k] = max( dp[j][k], dp[j - num_0][k - num_1] + 1);}}}return dp[m][n] ;}
};

518. 零钱兑换 II

518. 零钱兑换 II - 力扣(LeetCode)

描述

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

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

提示

1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000

代码解析

完全背包

一看到钱币数量不限,就知道这是一个完全背包。
dp[j]:凑成总金额j的货币组合数为dp[j]

dp[j] (考虑coins[i]的组合总和) 就是所有的dp[j - coins[i]](不考虑coins[i])相加。
所以递推公式:dp[j] += dp[j - coins[i]];

首先dp[0]一定要为1,dp[0] = 1是 递归公式的基础。
从dp[i]的含义上来讲就是,凑成总金额0的货币组合数为1。

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

这篇关于算法学习——LeetCode力扣动态规划篇3(494. 目标和、474. 一和零、518. 零钱兑换 II)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/866953

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

Java进阶学习之如何开启远程调式

《Java进阶学习之如何开启远程调式》Java开发中的远程调试是一项至关重要的技能,特别是在处理生产环境的问题或者协作开发时,:本文主要介绍Java进阶学习之如何开启远程调式的相关资料,需要的朋友... 目录概述Java远程调试的开启与底层原理开启Java远程调试底层原理JVM参数总结&nbsMbKKXJx

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...