代码随想录算法训练营第四十六天 139.单词拆分、多重背包(了解)、 背包总结

本文主要是介绍代码随想录算法训练营第四十六天 139.单词拆分、多重背包(了解)、 背包总结,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

代码随想录算法训练营第四十六天 | 139.单词拆分、多重背包(了解)、 背包总结

139.单词拆分

题目链接:139. 单词拆分 - 力扣(LeetCode)

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 字典中的单词就是物品,字符串s就是背包,物品能不能把背包装满?Set<String> wordDictSet = new HashSet(wordDict);boolean[] dp = new boolean[s.length() + 1];// dp[i]表示字符串 s 前 i个字符组成的字符串 s[0..i−1]是否能被空格拆分成若干个字典中出现的单词// 递推公式 //  if( [j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。dp[0] = true; // dp[0]就是递推的根基,dp[0]一定要为true, dp[0]没有意义// 先遍历背包/**如果求组合数就是外层for循环遍历物品,内层for遍历背包。如果求排列数就是外层for遍历背包,内层for循环遍历物品。 ✔*/for(int i = 1; i <= s.length(); ++i) {// 然后,我们开始遍历字符串 "leetcode" 的每个字符,同时对于每个字符,我们都会从字符头部遍历到当前字符的每个子字符串。for(int j = 0; j < i; ++j) {if(dp[j] && wordDictSet.contains(s.substring(j, i))) {// 判断s[0, j-1]是否存在于字典中,以及s[j, i-1]是否存在于字典中dp[i] = true;break;}}}return dp[s.length()];}
}

多重背包(了解)

题目链接:代码随想录 (programmercarl.com)

背包总结

题目链接:代码随想录 (programmercarl.com)

416.分割等和子集1

dp五部曲:

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

背包递推公式:

能否装满背包: dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

  • 动态规划:416.分割等和子集(opens new window)
  • 动态规划:1049.最后一块石头的重量 II

装满背包有几种方法:dp[j] += dp[j - nums[i]]

  • 动态规划:494.目标和(opens new window)
  • 动态规划:518. 零钱兑换 II(opens new window)
  • 动态规划:377.组合总和Ⅳ(opens new window)
  • 动态规划:70. 爬楼梯进阶版(完全背包)

装满背包后,能装的最大价值: dp[j] = max(dp[j], do[j - nums[i]] + values[i])

  • 动态规划:474.一和零

装满背包后,所用的最小物品个数: dp[j] = min(dp[j], dp[j - nums[i]])

  • 动态规划:322.零钱兑换(opens new window)
  • 动态规划:279.完全平方数(opens new window)

遍历顺序

01背包:遍历顺序无所谓

注意一下从二维到一维滚动数组的推导

完全背包:

先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的,题目稍有变化,两个for循环的先后顺序就不一样了。

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

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

相关题目如下:

  • 求组合数:动态规划:518.零钱兑换II(opens new window)
  • 求排列数:动态规划:377. 组合总和 Ⅳ (opens new window)、动态规划:70. 爬楼梯进阶版(完全背包)(opens new window)

如果求最小数,那么两层for循环的先后顺序就无所谓了,相关题目如下:

  • 求最小数:动态规划:322. 零钱兑换 (opens new window)、动态规划:279.完全平方数(opens new window)

对于背包问题,其实递推公式算是容易的,难是难在遍历顺序上,如果把遍历顺序搞透,才算是真正理解了

背包问题思维导图:

img

这篇关于代码随想录算法训练营第四十六天 139.单词拆分、多重背包(了解)、 背包总结的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

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

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

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

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

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

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

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

java常见报错及解决方案总结

《java常见报错及解决方案总结》:本文主要介绍Java编程中常见错误类型及示例,包括语法错误、空指针异常、数组下标越界、类型转换异常、文件未找到异常、除以零异常、非法线程操作异常、方法未定义异常... 目录1. 语法错误 (Syntax Errors)示例 1:解决方案:2. 空指针异常 (NullPoi

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

一文带你了解SpringBoot中启动参数的各种用法

《一文带你了解SpringBoot中启动参数的各种用法》在使用SpringBoot开发应用时,我们通常需要根据不同的环境或特定需求调整启动参数,那么,SpringBoot提供了哪些方式来配置这些启动参... 目录一、启动参数的常见传递方式二、通过命令行参数传递启动参数三、使用 application.pro

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论