day46-动态规划8-单词拆分问题

article/2024/7/17 22:28:32

139.单词拆分-完全背包问题区分求组合数和排列数

在这里插入图片描述
本题可以使用回溯算法进行暴力搜索,但是如何使用动态规划的思路进行求解呢。将字符串可以理解成一个容器,将单词可以当成物品,那么此时问题转化成利用物品能否装满容器的问题。这个时候由于返回的是True或者False,所以在搜索过程中需要将dp数组赋值成True或者False。
动归五步曲:

  1. dp[i]:长度为i的子串是否能被字典中的单词所组成。
  2. dp[0]=True
  3. 递推公式: dp[i] = dp[i] or dp[i-len(j)] and (s[i-len(j):i]==j),看当前状态是否用字典中的字符串进行表示。
  4. 遍历方式:
  5. 打印dp数组

思考:
返回什么结果那么dp数组的返回值就要设置成什么结果。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:# 转化成背包问题就是,单词的排列问题,单词的整体长度记作背包的承载重量# 长度为i的背包,可以用字典中的单词进行拆分。target = len(s)dp = [False] * (target + 1) #i的背包有几种装物品的方式dp[0] = Truefor i in range(1,target+1):for j in wordDict:if i >= len(j):dp[i] = dp[i] or dp[i-len(j)] and (s[i-len(j):i]==j)return dp[target]

多重背包问题-理论基础

多重背包定义:
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用,每件耗费的空间是Ci ,价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量,且价值总和最大。

多重背包非常类似于0-1背包:
每件物品最多有Mi件可用,把Mi件摊开,其实就是一个01背包问题了。

能在0-1背包问题的基础上,把多重背包的逻辑实现即可。

背包问题总结

总结来自于代码随想录

背包递推公式

问能否能装满背包(或者最多装多少):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.完全平方数(opens new window)

01背包

在动态规划:关于01背包问题,你该了解这些! (opens new window)中我们讲解二维dp数组01背包先遍历物品还是先遍历背包都是可以的,且第二层for循环是从小到大遍历。
和动态规划:关于01背包问题,你该了解这些!(滚动数组) (opens new window)中,我们讲解一维dp数组01背包只能先遍历物品再遍历背包容量,且第二层for循环是从大到小遍历。

一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的,大家需要注意!

完全背包

如果求组合数就是外层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)
对于背包问题,其实递推公式算是容易的,难是难在遍历顺序上,如果把遍历顺序搞透,才算是真正理解了。

198.打家劫舍

在这里插入图片描述

思考该问题的求解思路: 当前偷或者不偷的状态受到哪些状态的影响,如何利用这些状态建立递推关系。当前状态和前面状态会有一种依赖关系,那么这种依赖关系都是动规的递推公式。

动归五步曲:

  1. dp数组含义(结合问题求的结果是什么): dp[i]考虑下标i则能够偷到的最大的钱币。
  2. 递推公式:偷i的话 dp[i-2]+coin[i],不偷i-1 dp[i-1],dp数组的含义表示i之前能够得到的最大金币数。
  3. 初始化dp数组:dp[0] = nums[0],dp[1] = max(nums[1],nums[0])
  4. 遍历顺序
  5. 打印dp数组
class Solution:def rob(self, nums: List[int]) -> int:'''定义子问题:如何将原问题划分成一个一个的子问题,子问题就是对之前问题的解决,所以可以不用关注子问题,把注意力集中在此后问题的求解上写出子问题的递推关系确定 DP 数组的计算顺序'''N = len(nums)if N == 0:return 0if N == 1:return sum(nums)dp = [0]*(N+1)dp[0] = 0dp[1] = nums[0]for k in range(2,N+1):dp[k] = max(dp[k-1],dp[k-2]+nums[k-1])return dp[N]

213 打家劫舍II

由于线性数组出现了首尾相接的形式,为了解决该问题将线性数组进行拆分即可。先考虑前四个,再考虑后四个值,这样的话就可以对原始的数组进行拆分,在求解两个部分的最大值,即得到整体的最大值。主要思想就是让首尾元素不会相互影响。

class Solution:def traversal(self,nums):N = len(nums)if N == 0:return 0if N == 1:return sum(nums)dp = [0] * Ndp[0] = nums[0]dp[1] = max(nums[0],nums[1])for k in range(2,N):dp[k] = max(dp[k-1],dp[k-2]+nums[k])return dp[N-1]def rob(self, nums: List[int]) -> int:# 线性数组连成环,首尾相连,在这个环中偷的最大金币是多少。if len(nums) == 1:return nums[0]n = len(nums)left = self.traversal(nums[0:n-1])right = self.traversal(nums[1:n])return max(left,right)

http://www.ngui.cc/article/show-1200656.html

相关文章

淘宝监控竞品sku数据接口

电商竞品数据监控查询可以通过以下几个步骤实现: 确定需要监控的竞品:首先需要明确自己店铺的产品定位和竞争对手,选择需要监控的竞品。 选择监控工具:根据需求和预算选择适合自己的电商竞品数据监控工具,例如谷歌分析…

archive log list :报错的解决办法

装好oracle数据库之后, 没事在练习sql语句, 看看一些基本的字典表啊啥的 但是当我执行 archive log list这个的时候居然给我报错, 这句话的意思是: 查看数据库的备份和恢复策略,并确定归档文件的具体位置&#xff…

Arthas-Class/Classloader相关命令使用

tip:作为程序员一定学习编程之道,一定要对代码的编写有追求,不能实现就完事了。我们应该让自己写的代码更加优雅,即使这会费时费力。 开头: 我们先说下生产使用频率较高的有哪些:dump、jad、mc、retransfo…

Django框架:优缺点、实用场景及与Flask、FastAPI的对比

Django是一个使用Python语言编写的高级Web框架,它提供了快速开发、可重用和可维护的Web应用程序所需的一切组件。在本文中,我们将探讨Django的get和post请求、优缺点、实用场景以及与Flask、FastAPI的对比。 Django的get和post请求 在Django中&#xff0…

leetcode95--不同的二叉搜索树 II(java)

不同的二叉搜索树 II leetcode95 -- 不同的二叉搜索树 II题目描述 解题思路代码演示二叉树专题 leetcode95 – 不同的二叉搜索树 II 原题链接: https://leetcode.cn/problems/unique-binary-search-trees-ii/ 题目描述 给你一个整数 n ,请你生成并返回所有由 n 个节…

1036 Boys vs Girls(38行代码)

分数 25 全屏浏览题目 切换布局 作者 CHEN, Yue 单位 浙江大学 This time you are asked to tell the difference between the lowest grade of all the male students and the highest grade of all the female students. Input Specification: Each input file contai…

Task 异步编程教程

系列文章目录 Task 异步编程教程 系列文章目录前言常见的用法: Task 异步编程教程目录1. 异步编程基础1.1 异步操作的概念和优势1.2 使用 async 和 await 关键字定义异步方法1.3 异步方法的返回类型和特点 2. Task 类的基础2.1 Task 类的构造方法和静态方法2.2 Task…

Linux :: 【基础指令篇 :: 文件内容操作:(4)】:: head / tail 指令 :: 指定查看文件的部分内容 | 查看前 n 行内容

前言:本篇是 Linux 基本操作篇章的内容! 笔者使用的环境是基于腾讯云服务器:CentOS 7.6 64bit。 学习集: C 入门到入土!!!学习合集Linux 从命令到网络再到内核!学习合集 注&#xff…

Java学习路线(21)——网络通信

一、网络通信三件套 1、IP地址: 设备在网络中的地址,唯一标识 概念: Internet Protocal,简称为IP,全称“互联网协议地址”。 常见分类: IPv4(32位) 和 IPv6(128位&#…

从零开始的力扣刷题记录-第四十六天

力扣每日四题 507. 完美数-简单661. 图片平滑器-简单1652. 拆炸弹-简单1156. 单字符重复子串的最大长度-中等总结 507. 完美数-简单 题目描述: 对于一个 正整数,如果它和除了它自身以外的所有 正因子 之和相等,我们称它为 「完美数」。 给定…