力扣爆刷第128天之动态规划五连刷(一个零、零钱兑换、组合)

本文主要是介绍力扣爆刷第128天之动态规划五连刷(一个零、零钱兑换、组合),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣爆刷第128天之动态规划五连刷(一个零、零钱兑换、组合)

文章目录

      • 力扣爆刷第128天之动态规划五连刷(一个零、零钱兑换、组合)
      • 终结背包问题:这篇文章和上一篇。
      • 动态规划解题步骤:
      • 背包问题总结
      • 一、474. 一和零
      • 二、518. 零钱兑换 II
      • 三、377. 组合总和 Ⅳ
      • 四、57. 爬楼梯(第八期模拟笔试)
      • 五、322. 零钱兑换

终结背包问题:这篇文章和上一篇。

动态规划解题步骤:

  1. 确定dp数组(dp table)以及下标的含义。
  2. 确定递推公式。
  3. dp数组如何初始化。
  4. 确定遍历顺序。
  5. 举例推导dp数组。

背包问题总结

背包问题:一维数组,dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])。

01背包遍历顺序: 先物品后背包,物品正序,背包逆序。

如若背包正序则会出现同一个物品重复放入,如物品1重量为1,背包空间为1时放入了,背包空间为2时又放入了。
如果先背包后物品,为了避免重复放入背包依然是逆序,背包容量固定时,每种背包容量只能放入一个物品,即为最大的物品,小的物品都放不进来或者被覆盖了。

求组合数排列数:dp[j] += dp[j - nums[i]]

完全背包遍历顺序: 物品背包没有先后顺序,物品背包都是正序。因为同一个物品不限量可以放入多次,在背包采用正序中。

完全背包求组合数,物品在外,背包在内。求排列数,背包在外,物品在内。

一、474. 一和零

题目链接:https://leetcode.cn/problems/ones-and-zeroes/description/
思路:一和零是双重背包,本质上还是0 1 背包,只不过现在背包的容量有两个指标,所以还是0 1背包的套路,定义dp[i][j]数组表示容量为i个0和j个1的背包最多可以装下的字符串数量,故当前背包装物品的数量依赖于上一个容量较小时装的数量,具体是多少容量呢,当然是可以满足装下最大数量的容量,那到底是什么呢,就是例如有一个字符串有2个0和3个1,依赖于dp数组的定义,想让当前空间利用率最大,自然是把空间都占满,dp[i][j] = dp[i-2][j-3] + 1。故递推公式为dp[i][j] = Math.max(dp[i][j], dp[i-nums[0]][j-nums[1]] + 1);

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(String s : strs) {int[] nums = countNums(s);for(int i = m; i >= nums[0]; i--) {for(int j = n; j >= nums[1]; j--) {dp[i][j] = Math.max(dp[i][j], dp[i-nums[0]][j-nums[1]] + 1);}}}return dp[m][n];}int[] countNums(String s) {int[] nums = new int[2];int a = 0, b = 0;for(int i = 0; i < s.length(); i++) {if(s.charAt(i) == '0') {a++;}else{b++;}}nums[0] = a;nums[1] = b;return nums;}
}

二、518. 零钱兑换 II

题目链接:https://leetcode.cn/problems/coin-change-ii/description/
思路:本题物品数量无限是完全背包,完全背包求组合数。完全背包物品和背包都是正序,如果求组合数,物品在外,背包在内。如果求排列数,背包在外,物品在内。

class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount+1];dp[0] = 1;for(int i = 0; i < coins.length; i++) {for(int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}

三、377. 组合总和 Ⅳ

题目链接:https://leetcode.cn/problems/combination-sum-iv/description/
思路:和上一题类似,也是物品无限使用,是完全背包,但是不同的是求的是排列数。物品和背包都正序,背包在外,物品在内。

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

四、57. 爬楼梯(第八期模拟笔试)

题目链接:https://kamacoder.com/problempage.php?pid=1067
思路:本题是总楼梯数是背包总数,每次可以爬的楼梯数(1 <= m < n),求有多少种爬楼的方法。所以很明显是完全背包求排列数,爬楼梯的方法1,2和2,1明细是两种方法。所以直接套公式,完全背包求排列数,背包在外,物品在内。背包和物品都正序。
同时推荐一下卡码网,可以练习ACM模式。

import java.lang.*;
import java.util.*;class Main{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt(), m = scan.nextInt();int[] dp = new int[n+1];dp[0] = 1;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {if(i >= j) {dp[i] += dp[i-j];}}}System.out.println(dp[n]);} 
}

五、322. 零钱兑换

题目链接:https://leetcode.cn/problems/coin-change/description/
思路:本题是物品数量无限,完全背包。对于完全背包求组合数,物品在外,背包在内,求排列数,背包在外,物品在内。
其他的比如求能装的最大最小个数,物品和背包没有顺序要求,所以在内在外都行,其他的没有了。

class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];Arrays.fill(dp, Integer.MAX_VALUE);dp[0] = 0;for(int i = 0; i < coins.length; i++) {for(int j = coins[i]; j <= amount; j++) {if(dp[j-coins[i]] == Integer.MAX_VALUE) continue;dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);}}return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];}
}

这篇关于力扣爆刷第128天之动态规划五连刷(一个零、零钱兑换、组合)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删