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

代码随想录算法训练营第四十六天【动态规划part08】 | 139.单词拆分、背包总结

139.单词拆分

题目链接:

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

求解思路:

单词是物品,字符串s是背包,单词能否组成字符串s,就是问物品能不能把背包装满。

动规五部曲

  1. 确定dp数组及其下标含义:字符串长度为i,dp[i] 表示可以字符串可以拆分为一个或多个在字典中出现的单词
  2. 确定递推公式:如果确定dp[j] 是true,且[j, i]这个区间的子串出现在字典里,那么dp[i]一定是true。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true
  3. dp数组的初始化:dp[0] = true,递推的根基;其他下表都初始化为false
  4. 确定遍历顺序:本题强调顺序,因此是排列问题,所以先遍历背包,再遍历物品;因为是完全背包,所以正序遍历
  5. 举例推导dp:以输入: s = "leetcode", wordDict = ["leet", "code"]为例,dp状态如图

代码:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size()+1, false);dp[0] = true;for (int i = 1; i <= s.size(); i++){for (int j = 0; j < i; j++){string word = s.substr(j, i-j);if (wordSet.find(word) != wordSet.end() && dp[j]){dp[i] = true;}}}return dp[s.size()];}
};

背包总结

背包递推公式

问能否能装满背包(或者最多装多少):dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ,对应题目如下:

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

问装满背包有几种方法:dp[j] += dp[j - nums[i]] ,对应题目如下:

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

问背包装满最大价值:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); ,对应题目如下:

  • 动态规划:474.一和零(opens new window)

问装满背包所有物品的最小个数:dp[j] = min(dp[j - coins[i]] + 1, dp[j]); ,对应题目如下:

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

遍历顺序

01背包

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

一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历。

完全背包

纯完全背包的一维dp数组实现,先遍历物品还是先遍历背包都是可以的,且第二层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)

相关文章:

代码随想录算法训练营第四十六天【动态规划part08】 | 139.单词拆分、背包总结

139.单词拆分 题目链接&#xff1a; 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 求解思路&#xff1a; 单词是物品&#xff0c;字符串s是背包&#xff0c;单词能否组成字符串s&#xff0c;就是问物品能不能把背包装满。 动规五部曲 确定dp数…...

go语言基础 break和contine区别

背景 break和continue是编程语言的标准语法&#xff0c;几乎在所有的语言都有类似的用法。 go语言及所有其他编程语言for循环或者其他循环 区别 for i : 0; i < 10; i {if i 5 {continue}fmt.Println(i)for j : 0; j < 3; j {fmt.Println(strconv.Itoa(j) "a&q…...

vue3父子组件通过$parent与ref通信

父组件 <template><div><h1>ref与$parents父子组件通信 {{ parentMoney }}</h1><button click"handler">点击我子组件的值会减20</button><hr><child ref"children"></child></div> </te…...

PHP中的常见的超全局变量

PHP是一种广泛使用的服务器端脚本语言&#xff0c;它被用于开发各种Web应用程序。在PHP中&#xff0c;有一些特殊的全局变量&#xff0c;被称为超全局变量。超全局变量在整个脚本中都是可用的&#xff0c;无需使用global关键字来访问它们。在本文中&#xff0c;我们将深入了解P…...

leetcode9.回文数

回文数 0.题目1.WJQ的思路2.实现过程2.0 原始值怎么一个个取出来&#xff1f;2.1 取出来的数如何存到新的数字后面&#xff1f;2.2完整的反转得到新数的过程 3.完整的代码4.可运行的代码5.算法还可以优化的部分 0.题目 给你一个整数 x &#xff0c;如果 x 是一个回文整数&…...

springboot(ssm大学生二手电子产品交易平台 跳蚤市场系统Java(codeLW)

springboot(ssm大学生二手电子产品交易平台 跳蚤市场系统Java(code&LW) 开发语言&#xff1a;Java 框架&#xff1a;ssm/springboot vue JDK版本&#xff1a;JDK1.8&#xff08;或11&#xff09; 服务器&#xff1a;tomcat 数据库&#xff1a;mysql 5.7&#xff08;或…...

关于微信小程序中如何实现数据可视化-echarts动态渲染

移动端设备中&#xff0c;难免会涉及到数据的可视化展示、数据统计等等&#xff0c;本篇主要讲解原生微信小程序中嵌入echarts并进行动态渲染&#xff0c;实现数据可视化功能。 基础使用 首先在GitHub上下载echarts包 地址&#xff1a;https://github.com/ecomfe/echarts-for…...

在Windows WSL (Linux的Windows子系统)上运行的Ubuntu如何更改主机名

在Windows 安装的Ubuntu&#xff0c;如何修改主机名。有列了两种方法&#xff0c;提供给大家参照。 文章目录 方法一&#xff1a;hostname指令修改方法二&#xff1a;修改配置文件修改hostnanmewsl.conf 文件配置选项推荐阅读 方法一&#xff1a;hostname指令修改 hostname指…...

如何使用内网穿透将Tomcat网页发布到公共互联网上【内网穿透】

文章目录 前言1.本地Tomcat网页搭建1.1 Tomcat安装1.2 配置环境变量1.3 环境配置1.4 Tomcat运行测试1.5 Cpolar安装和注册 2.本地网页发布2.1.Cpolar云端设置2.2 Cpolar本地设置 3.公网访问测试4.结语 前言 Tomcat作为一个轻量级的服务器&#xff0c;不仅名字很有趣&#xff0…...

网络入门---网络的大致了解

目录标题 网络发展的简单认识协议作用的理解协议的本质什么是协议分层网络通信所面对的问题OSI七层模型TCP/IP模型协议报头的理解局域网通信局域网通信基本原理报头的问题局域网的特点跨网的网络链接如何查看mac地址 网络发展的简单认识 通过之前的学习我们知道计算机是给人提…...

构建沉浸式 AI 文本编辑器:开源 3B 编辑器的设计原则与思路

借助于在 AutoDev 与 IDE 上的 AI 沉浸式体验设计&#xff0c;我们开始构建一个 AI 原生的文本编辑器&#xff0c;以探索沉浸式创作体验。其适用于需求编写、架构文档等等文档场景&#xff0c;以加速软件开发中的多种角色的日常工作。 GitHub&#xff1a;https://github.com/un…...

【从删库到跑路 | MySQL总结篇】表的增删查改(进阶上)

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【MySQL学习专栏】&#x1f388; 本专栏旨在分享学习MySQL的一点学习心得&#xff0c;欢迎大家在评论区讨论&#x1f48c; 目录 一、数据…...

[每周一更]-(第74期):Docker-compose 部署Jenkins容器-英文版及错误纠错

1、前文概要 通过物理机部署Jenkins前文已经讲过&#xff08;地址&#xff1a;[Jenkins] 物理机 安装 Jenkins&#xff09;&#xff0c;也已经公司内部平稳运行若干年&#xff0c;考虑到容器化的使用场景&#xff0c;部分项目都采用容器运行&#xff0c;开始考虑部署容器化的J…...

MySQL日期函数sysdate()与now()的区别,获取当前时间,日期相关函数

select sleep(2) as datetime union all select sysdate() -- sysdate() 返回的时间是当前的系统时间&#xff0c;而 now() 返回的是当前的会话时间。 union all select now() -- 等价于 localtime,localtime(),localtimestamp,localtimestamp(),current_timestamp,curre…...

邦芒解析:面试怎么谈自身优缺点

在面试时&#xff0c;当被问到你的优缺点时&#xff0c;你可以这样回答&#xff1a; 优点&#xff1a; 我的工作能力强&#xff0c;能够高效地完成任务。我对技术有热情&#xff0c;喜欢学习新的技能和知识。我善于沟通&#xff0c;能够与不同背景的人进行有效沟通。我注重细节…...

【libGDX】加载G3DJ模型

1 前言 libGDX 提供了自己的 3D 格式模型文件&#xff0c;称为 G3D&#xff0c;包含 g3dj&#xff08;Json 格式&#xff09;和 g3db&#xff08;Binary 格式&#xff09;文件&#xff0c;官方介绍见 → importing-blender-models-in-libgdx。 对于 fbx 文件&#xff0c;libGDX…...

0基础学习VR全景平台篇第123篇:VR视频航拍补天 - PR软件教程

上课&#xff01;全体起立~ 大家好&#xff0c;欢迎观看蛙色官方系列全景摄影课程&#xff01; 嗨&#xff0c;大家好&#xff0c;今天我们来介绍【航拍VR视频补天】。之前已经教给了大家如何处理航拍图片的补天&#xff0c;肯定有很多小伙伴也在好奇&#xff0c;航拍的VR视频…...

webpack打包三方库直接在html里面使用

场景&#xff1a;我是小程序中使用wxmp-rsa库进行加密&#xff0c;然后在html里面解密 我就想把wxmp-rsa库打包到一个js里面&#xff0c;然后在html里面直接引入使用。 webpack配置 const path require("path"); const MiniCssExtractPlugin require("mini-…...

Redis使用increment方法返回null的原因以及解决方案

public static void main(String[] args) {redisTemplate.setEnableTransactionSupport(true); //开启事务支持redisTemplate.multi(); //标记事务块的开始redisTemplate.opsForValue().set("name","zs");redisTemplate.opsForValue().set("pass&qu…...

springMVC,什么是Spring MVC? Spring MVC的主要组件? springMVC工作原理/流程 MVC框架

文章目录 springMVC什么是Spring MVC&#xff1f;Spring MVC的主要组件&#xff1f;springMVC工作原理/流程MVC框架 今天以这篇文章简单和大家聊聊springMVC相关的内容&#xff0c;和原理&#xff0c;以及框架&#xff1b; springMVC 什么是Spring MVC&#xff1f; Spring MV…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...