【随想录】Day46—第九章 动态规划part08

2024-05-14 02:36

本文主要是介绍【随想录】Day46—第九章 动态规划part08,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 题目1: 139. 单词拆分
    • 1- 思路
    • 2- 题解
      • ⭐单词拆分——题解思路
  • 题目2: 完全背包
    • 题目3: 背包问题总结
    • 总结


题目1: 139. 单词拆分

  • 题目链接:139. 单词拆分

1- 思路

目标

  • 根据字符串 String sList<String> wordDict 来判断是否能通过 wordDict 组成 s

动规五部曲

  • 1. 确定 dp 数组含义
    • 定义:根据字符串 s 的长度定义 dp[i] ——> 最终返回 dp[s.length()]
    • 含义:长度为 s 的字符串,是否能由数组 wordDict 组成
  • 2. 确定递推公式
    • dp[i] 是 true 还是 false 依赖于其前面长度为 j 的字符串 dp[j]
    • 如果 dp[j] = true 且 ,i-jwordDict 中长度的单词 ——> 则 dp[i] = true
  • 3. dp 数组初始化
    • dp[0] = true ,长度为 0 为了 dp 数组的推导
    • 非 0 下标的 dp 数组初始化为 false
  • 4. 遍历顺序(所求为组合,因此需要先遍历背包再遍历物品)
    • 装满背包是对字符串的顺序是有要求的,因此本题目相当于求 排列问题 ——> 先遍历背包,再遍历物品
    • ① 先遍历背包 for(int i = 1 ; i <= s.length() ; i++)
    • ② 再遍历物品 for(int j = 0; j < i ; j++)
      • 此时需要对 ij 中的字符串进行一个截取 ——> String str = s.subString(j,i-j)
    • 遍历内部逻辑:
      • 如果 dp[j] = true 且 ,i-jwordDict 中长度的单词 ——> 则 dp[i] = true
      • dp[j] = true

2- 题解

⭐单词拆分——题解思路

在这里插入图片描述

class Solution {public boolean wordBreak(String s, List<String> wordDict) {// 背包 s// 商品 wordDictHashSet<String> set = new HashSet<>(wordDict);// 1. 定义 dp 数组确定含义boolean[] dp = new boolean[s.length()+1];// 2. 确定递推公式// 如果 dp[j] = true 且  的子串在 wordDict 中 则 dp[j] = true// 3. 初始化dp[0] = true;// 4. 遍历顺序,排列问题// 先背包 后物品for(int i = 1 ; i <= s.length();i++){for(int j = 0 ; j <i && !dp[i];j++){if(set.contains(s.substring(j,i)) && dp[j]){dp[i] = true;}}}return dp[s.length()];}
}

题目2: 完全背包

  • LeetCode无原题

题目3: 背包问题总结

  • 主要常见的背包问题有 ①01背包②完全背包③多重背包

总结

这篇背包问题总结篇是对背包问题的高度概括,讲最关键的两部:递推公式和遍历顺序,结合力扣上的题目全都抽象出来了
而且每一个点,我都给出了对应的力扣题目
最后如果你想了解多重背包,可以看这篇动态规划:关于多重背包,你该了解这些!(opens new window),力扣上还没有多重背包的题目,也不是面试考察的重点。
如果把我本篇总结出来的内容都掌握的话,可以说对背包问题理解的就很深刻了,用来对付面试中的背包问题绰绰有余!
背包问题总结:


这篇关于【随想录】Day46—第九章 动态规划part08的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

VUE动态绑定class类的三种常用方式及适用场景详解

《VUE动态绑定class类的三种常用方式及适用场景详解》文章介绍了在实际开发中动态绑定class的三种常见情况及其解决方案,包括根据不同的返回值渲染不同的class样式、给模块添加基础样式以及根据设... 目录前言1.动态选择class样式(对象添加:情景一)2.动态添加一个class样式(字符串添加:情

SpringCloud配置动态更新原理解析

《SpringCloud配置动态更新原理解析》在微服务架构的浩瀚星海中,服务配置的动态更新如同魔法一般,能够让应用在不重启的情况下,实时响应配置的变更,SpringCloud作为微服务架构中的佼佼者,... 目录一、SpringBoot、Cloud配置的读取二、SpringCloud配置动态刷新三、更新@R

如何用Python绘制简易动态圣诞树

《如何用Python绘制简易动态圣诞树》这篇文章主要给大家介绍了关于如何用Python绘制简易动态圣诞树,文中讲解了如何通过编写代码来实现特定的效果,包括代码的编写技巧和效果的展示,需要的朋友可以参考... 目录代码:效果:总结 代码:import randomimport timefrom math

Java中JSON字符串反序列化(动态泛型)

《Java中JSON字符串反序列化(动态泛型)》文章讨论了在定时任务中使用反射调用目标对象时处理动态参数的问题,通过将方法参数存储为JSON字符串并进行反序列化,可以实现动态调用,然而,这种方式容易导... 需求:定时任务扫描,反射调用目标对象,但是,方法的传参不是固定的。方案一:将方法参数存成jsON字

.NET利用C#字节流动态操作Excel文件

《.NET利用C#字节流动态操作Excel文件》在.NET开发中,通过字节流动态操作Excel文件提供了一种高效且灵活的方式处理数据,本文将演示如何在.NET平台使用C#通过字节流创建,读取,编辑及保... 目录用C#创建并保存Excel工作簿为字节流用C#通过字节流直接读取Excel文件数据用C#通过字节

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d