代码随想录算法训练营 动态规划part08

一、单词拆分 

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

将字符串 s 长度记为 n,wordDict 长度记为 m。为了方便,我们调整字符串 s 以及将要用到的动规数组的下标从 1 开始。

定义 f[i] 为考虑前 i 个字符,能否使用 wordDict 拼凑出来:当 f[i]=true 代表 s[1...i] 能够使用 wordDict 所拼凑,反之则不能。

不失一般性考虑 f[i] 该如何转移:由于 f[i] 需要考虑 s[1...i] 范围内的字符,若 f[i]为 True 说明整个 s[1...i] 都能够使用 wordDict 拼凑,自然也包括最后一个字符 s[i] 所在字符串 sub。

我们可以枚举最后一个字符所在字符串的左端点 jjj,若 sub=s[j...i] 在 wordDict 中出现过,并且 f[j−1]=True,说明 s[0...(j−1)] 能够被拼凑,并且子串 sub 也在 wordDict,可得 f[i] = True。

为了快速判断某个字符是否在 wordDict 中出现,我们可以使用 Set 结构对 wordDict[i] 进行转存。

class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> set = new HashSet<>();for (String word : wordDict) set.add(word);int n = s.length();boolean[] f = new boolean[n + 10];f[0] = true;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i && !f[i]; j++) {String sub = s.substring(j - 1, i);if (set.contains(sub)) f[i] = f[j - 1]; }}return f[n];}
}

二、背包问题总结

代码随想录 (programmercarl.com)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

linux进程杀不死

项目场景&#xff1a; 虚拟机 问题描述 linux进程杀不死 无反应 原因分析&#xff1a; 进程僵死zombie 解决方案&#xff1a; 进proc或者find命令找到进程所在地址 cat status查看进程杀死子进程

多输入多输出 | MATLAB实现CNN-BiGRU卷积双向门控循环单元多输入多输出

多输入多输出 | MATLAB实现CNN-BiGRU卷积双向门控循环单元多输入多输出 目录 多输入多输出 | MATLAB实现CNN-BiGRU卷积双向门控循环单元多输入多输出预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 MATLAB实现CNN-BiGRU卷积双向门控循环单元多输入多输出&#xf…

Otter改造 增加springboot模块和HTTP调用功能

环境搭建 & 打包 环境搭建&#xff1a; 进入 $otter_home/lib 目录执行&#xff1a;bash install.sh 打包&#xff1a; 进入$otter_home目录执行&#xff1a;mvn clean install -Dmaven.test.skip -Denvrelease发布包位置&#xff1a;$otter_home/target 项目背景 阿里…

「大数据-0」虚拟机VMware安装、配置、使用、创建大数据集群教程

目录 一、下载VMware Wworkstation Pro 16 二、安装VMware Wworkstation Pro 16 三、检查与设置VMware的网卡 1. 检查 2. 设置VMware网段 四、在VMware上安装Linux虚拟机 五、对安装好的虚拟机进行设置 1. 打开设置 2. 设置中文 3. 修改字体大小 4. 修改终端字体大小 5. 关闭虚…

十、性能测试之数据库测试

性能测试之数据库测试 一、 数据库分类二、 mysql安装及密码的修改1、安装&#xff1a;数据库的版本 mysql5.7版方法1&#xff1a;直接安装方法2&#xff1a;使用rpm包安装方法3&#xff1a;docker方式安装 2、修改数据库的密码3、创建库4、创建表 三、存储引擎1、InnoDB特点 2…

进入数据结构的世界

数据结构和算法的概述 一、什么是数据结构二、什么是算法三、如何去学习数据结构和算法四、算法的时间复杂度和空间复杂度4.1 算法效率4.2 大O的渐进表示法4.3 时间复杂度4.4 空间复杂度4.5 常见复杂度对比 一、什么是数据结构 数据结构是计算机存储、组织数据的方式。&#x…

java框架-Springboot3-基础特性+核心原理

文章目录 java框架-Springboot3-基础特性核心原理profiles外部化配置生命周期监听事件触发时机事件驱动开发SPISpringboot容器启动过程自定义starter java框架-Springboot3-基础特性核心原理 profiles 外部化配置 生命周期监听 事件触发时机 事件驱动开发 Component public c…

Hana SQL Format 的希望

以前一直吐槽Hana Sql 无法进行代码格式化&#xff0c;没有abap code的pretty print功能&#xff0c;对运维和理解代码来说都很不方便。这个情况在abap cleaner里得到改善。 现阶段他们abap的美化做的比原始的pretty print还要好&#xff0c;我基本已经不用pretty print&#x…

获取文件上次访问时间

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Java源码 public void testGetFileTime() {try {String string "E://test.txt";File file new File(string);Path path file.toPath();BasicFileAttributes ba…

TypeScript- 对于对象键名(包括函数键值)不确定的接口,可以使用字符串索引的形式

AXIOS树配置项 有一个需求&#xff0c;通过JSON数据&#xff0c;第一层是对应的页面对象&#xff08;比如是用户页面&#xff09;&#xff0c;第二层是该页面的API请求名&#xff08;比如用户的增删改查&#xff09;&#xff0c;第三层是该API的配置信息&#xff08;比如&…

系统安装(一)CentOS 7 本地安装

CentOS与Ubuntu并称为Linux最著名的两个发行版&#xff0c;但由于笔者主要从事深度学习图像算法工作&#xff0c;Ubuntu作为谷歌和多数依赖库的亲儿子占据着最高生态位。但最近接手的一个项目里&#xff0c;甲方指定需要在CentOS7上运行项目代码&#xff0c;笔者被迫小小cos了一…

scikit-learn机器学习算法封装

K近邻算法 K-最近邻&#xff08;KNN&#xff09;是一种有监督的机器学习算法&#xff0c;可用于解决分类和回归问题。它基于一个非常简单的想法&#xff0c;数据点的值由它周围的数据点决定。考虑的数据点数量由k值确定。因此&#xff0c;k值是算法的核心。 我们现在已经知道。…

mac安装chromedriver驱动详细步骤

1.查看浏览器版本 2.下载驱动 3.安装驱动 4.MacOS无法打开“chromedriver”&#xff0c;因为无法验证开发者 1.查看浏览器版本 在这里插入图片描述 2.下载驱动 下载驱动地址&#xff1a;链接: http://chromedriver.storage.googleapis.com/index.html. 下载和浏览器版本一致的…

解决因为修改SELINUX配置文件出错导致Faild to load SELinux poilcy无法进入CentOS7系统的问题

一、问题 最近学习Kubernetes&#xff0c;需要设置永久关闭SELINUX,结果修改错了一个SELINUX配置参数&#xff0c;关机重新启动后导致无法进入CentOS7系统&#xff0c;卡在启动进度条界面。 二、解决 多次重启后&#xff0c;在启动日志中发现 Faild to load SELinux poilcy…

Windows专业版的Docker下载、安装与启用Kubenetes、访问Kubernetes Dashboard

到Docker 官网https://www.docker.com/ 下载windows操作系统对应的docker软件安装 Docker Desktop Installer-Win.exe 2023-09版本是4.23 下载后双击安装 重启windows后&#xff0c;继续安装 接受服务继续安装 解决碰到的Docker Engine stopped 打开 控制面板》程序》启用或关…

基于微服务的第二课堂管理系统(素质拓展学分管理平台)SpringCloud、SpringBoot 分布式,微服务

基于微服务的第二课堂管理系统 一款真正的企业级开发项目&#xff0c;采用标准的企业规范开发&#xff0c;有项目介绍视频和源码&#xff0c;需要学习的同学可以拿去学习&#xff0c;这是一款真正可以写在简历上的校招项目&#xff0c;能够真正学到东西的一个项目&#xff0c;话…

SpringBoot开发实战(微课视频版)

ISBN: 978-7-302-52819-7 编著&#xff1a;吴胜 页数&#xff1a;311页 阅读时间&#xff1a;2023-06-24 推荐指数&#xff1a;★★★★☆ 本文介绍SpringBoot 2.0.5 、JDK 1.8&#xff0c;虽然现在已经不维护了&#xff0c;但是大体的流程还是对口的&#xff0c; 而且书里面讲…

左神高阶进阶班4 (尼姆博弈问题、k伪进制、递归到动态规划、优先级结合的递归套路、子串的递归套路,子序列的递归套路,动态规划的压缩技巧)

目录 【案例1 尼姆博弈问题】 【题目描述】 【思路解析】 【代码实现】 【案例2 k伪进制问题】 【题目描述】 【思路解析】 【代码实现】 【案例3 最大路径和】 【题目描述】 【思路解析】 【代码实现】 【案例4 优先级的递归套路】 【题目描述】 【思路解析】…

黑马JVM总结(二十三)

&#xff08;1&#xff09;字节码指令-init 方法体内有一些字节&#xff0c;对应着将来要由java虚拟机执行方法内的代码&#xff0c;构造方法里5个字节代码&#xff0c;main方法里有9个字节的代码 java虚拟机呢内部有一个解释器&#xff0c;这个解释器呢可以识别平台无关的字…

整合车辆出险报告Api接口,轻松管理车险理赔!

随着车辆保有量的不断增加&#xff0c;车辆出险的情况也越来越普遍。对于车主来说&#xff0c;如何高效地管理车险理赔&#xff0c;处理保险事故是非常重要的。这时候我们就可以借助整合车辆出险报告API接口&#xff0c;实现快速定位理赔信息&#xff0c;轻松管理车险理赔。 一…