当前位置: 首页 > news >正文

代码随想录第46天 | 139. 单词拆分、多重背包

139. 单词拆分

  1. 确定dp数组以及下标的含义
    dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

  2. 确定递推公式
    如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i )。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  1. dp数组如何初始化
    从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。

那么dp[0]有没有意义呢?

dp[0]表示如果字符串为空的话,说明出现在字典里。

但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

  1. 确定遍历顺序
    题目中说是拆分为一个或多个在字典中出现的单词,所以这是完全背包。

还要讨论两层for循环的前后顺序。

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

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

/*** @param {string} s* @param {string[]} wordDict* @return {boolean}*/
var wordBreak = function (s, wordDict) {let dp = Array(s.length + 1).fill(false);dp[0] = true;for (let i = 0; i <= s.length; i++) {for (let j = 0; j < wordDict.length; j++) {if (i >= wordDict[j].length) {if (s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) {dp[i] = true}}}}return dp[s.length];
};

相关文章:

代码随想录第46天 | 139. 单词拆分、多重背包

139. 单词拆分 确定dp数组以及下标的含义 dp[i] : 字符串长度为i的话&#xff0c;dp[i]为true&#xff0c;表示可以拆分为一个或多个在字典中出现的单词。 确定递推公式 如果确定dp[j] 是true&#xff0c;且 [j, i] 这个区间的子串出现在字典里&#xff0c;那么dp[i]一定是tru…...

Unreal View Model结合GAS使用

这个东西真的难用&#xff0c;各种问题&#xff0c;记录下 官方文档 bilibili教学 开启插件 插件开启 Viewmodel&#xff1a; build.cs内PublicDependencyModuleNames加上ModelViewViewModel 创建ViewModel类 #pragma once#include "CoreMinimal.h" #include &quo…...

Spring-Cloud-Loadblancer详细分析_2

LoadBalancerClients 终于分析到了此注解的作用&#xff0c;它是实现不同服务之间的配置隔离的关键 Configuration(proxyBeanMethods false) Retention(RetentionPolicy.RUNTIME) Target({ ElementType.TYPE }) Documented Import(LoadBalancerClientConfigurationRegistrar…...

uniapp 左右滑动切换页面并切换tab

实现效果如图 要实现底部内部的左右滑动切换带动上方tab栏的切换&#xff0c;并且下方内容要实现纵向滚动 &#xff0c;所以需要swiper&#xff0c;swiper-item,scroll-view组合使用 tab栏部分 <view class"tabs"><view class"tab_item" v-for&…...

FinClip 支持小程序维度域名配置;桌面端体验活动进行中

FinClip 的使命是使您&#xff08;业务专家和开发人员&#xff09;能够通过小程序解决关键业务流程挑战&#xff0c;并完成数字化转型的相关操作。不妨让我们看看在本月的产品与市场发布亮点&#xff0c;看看是否有助于您实现目标。 产品方面的相关动向&#x1f447;&#x1f…...

已有公司将ChatGPT集成到客服中心以增强用户体验

Ozonetel正在利用ChatGPT来改善客户体验。该公司表示&#xff0c;他们通过使用ChatGPT收集与客户互动过程收集的“语料”能够更有针对性地提高服务效率&#xff0c;提供个性化的用户体验&#xff0c;并实现更高的客户满意度。[1] 通过这套解决方案&#xff0c;客服中心将拥有一…...

108. 将有序数组转换为二叉搜索树

文章目录 题目描述思路解答&#xff08;c&#xff09;结果 题目描述 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二…...

视频分辨率: UXGA/SVGA/VGA/QVGA/QQVGA

视频分辨率除了常见的720p/2K/4K外, 还有VGA系列的分辨率 相关字段含义: V——Video &#xff08;视频&#xff09; G——Graphics&#xff08;图像&#xff09; A——Array&#xff08;阵列&#xff09; S——Super(超级) X——Extended(扩展) U——Ultra(终极) W——Wide&am…...

Leecode力扣27数组移除元素

题目链接&#xff1a;力扣 最终可运行的代码1&#xff1a;暴力法 class Solution { public:int removeElement(vector<int>& nums, int val) {int index0;int numnums.size();while(index<nums.size()-1){if(nums[index]val){int jindex;num--;while(j<nums.…...

百度云盘发展历程与影响

摘要&#xff1a; 百度云盘作为中国领先的云存储与共享服务提供商&#xff0c;自其创立至今经历了多个阶段的发展与变革。本论文通过对百度云盘的历史回顾与分析&#xff0c;探讨了其在技术、商业模式、用户体验以及对社会的影响等方面的演变。同时&#xff0c;还分析了在竞争激…...

SpringBoot复习:(33)WebMvcAutoconfiguration内部静态类WebMvcAutoConfigurationAdapter

WebMvcAutoconfiguration内部静态类WebMvcAutoConfigurationAdapter实现了WebMvcConfigurer接口&#xff0c;重写了一些方法&#xff0c;也就是默认对Spring Mvc进行了一些配置: 该静态类上有个**Import**注解&#xff1a; Import(EnableWebMvcConfiguration.class) 它的父类…...

f1tenth仿真2

起点(0.192,0.201) 终点(9.902,5.148) 起点(9.902,5.148) 终点(-13.289,7.058) 起点(-13.289,7.058) 终点(-13.289,0.201) 起点(-13.289,0.201) #! /usr/bin/env python import time from numba import jit import math import rospy import numpy as…...

exec族函数

本节学习exec族函数&#xff0c;并大量参考了以下链接&#xff1a; linux进程---exec族函数(execl, execlp, execle, execv, execvp, execvpe)_云英的博客-CSDN博客 exec族函数函数的作用 我们用fork函数创建新进程后&#xff0c;经常会在新进程中调用exec函数去执行另外一个程…...

dbm与mw转换

功率值10^(dBm值/10)&#xff0c;单位mW。 对于-5dBm&#xff0c;其功率值为0.3162 mW。 dBm 10 * lg(mW&#xff09;...

【Linux】多线程之单例模式

多线程之单例模式 什么是设计模式&#xff0c;都有哪些设计模式单例模式饿汉模式懒汉模式 什么是设计模式&#xff0c;都有哪些设计模式 设计模式就是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理…...

Vision Transformer模型入门

Vision Transformer模型入门 一、Vision Transformer 模型1&#xff0c;Embedding 层结构详解2&#xff0c;Transformer Encoder 详解3&#xff0c;MLP Head 详解 二、ViT-B/16 网络结构三、Hybrid 模型详解四、ViT 模型搭建参数 一、Vision Transformer 模型 总体三个模块&am…...

如何使用 Go 获取 URL 的参数,以及使用时的问题

Go 获取 URL 参数也很容易&#xff0c;但是由于 Go 有严格的数据类型和错误管理&#xff0c;所以在使用时会些微有些复杂。所以本文不仅会讲如何获取 URL 的参数&#xff0c;也会讲在使用时的一些问题。 首先假设 URL 是https://www.example.com/?keywordabc&id12。 其他…...

Linux驱动-基于QT控制LED灯

Linux驱动-基于QT控制LED灯 环境搭建LED驱动程序基于总线设备模型基于设备树 QT界面编程测试 环境搭建 平台 韦东山100ask imax6ull pro && 大象嵌入式开发板Build Root 使用Build root编译image&#xff0c;具体配置可参考《嵌入式Linux应用开发完全手册-IMX6ULL开发…...

布隆过滤器的原理和应用场景

目录 1 原理 2 代码示例 3 位数组 4 布隆过滤器的实际应用场景 1 原理 布隆过滤器&#xff08;Bloom Filter&#xff09;是一种数据结构&#xff0c;用于快速判断一个元素是否存在于一个集合中&#xff0c;具有高效的插入和查询操作。它的设计目的是在空间效率和查询效率之…...

ElasticSearch学习

一&#xff0c;简介 ES&#xff08;elaticsearch简写&#xff09;&#xff0c; Elasticsearch是一个开源的高扩展的分布式全文检索引擎&#xff0c;它可以近乎实时的存储、检索数据&#xff1b;本身扩展性很好&#xff0c;可以扩展到上百台服务器&#xff0c;处理PB级别的数据…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...