做安全宣传的是什么网站,内蒙古省呼和浩特网站建设,电子商务网络营销论文,网络营销推广方法脑24金手指效率高文章目录 0. 动态规划#x1f3af;五个思考步骤 和 注意事项#x1f3af;技巧优化思路 1. 子数组系列1.1 乘积为正数的最长子数组长度1.2 等差数列划分1.3 最长湍流子数组1.4 单词拆分1.5 环绕字符串中的子字符串 0. 动态规划
介绍本篇之前#xff0c;我想先用人话叙述一般… 文章目录 0. 动态规划五个思考步骤 和 注意事项技巧优化思路 1. 子数组系列1.1 乘积为正数的最长子数组长度1.2 等差数列划分1.3 最长湍流子数组1.4 单词拆分1.5 环绕字符串中的子字符串 0. 动态规划
介绍本篇之前我想先用人话叙述一般解决动态规划问题的思路
动态规划的问题本身有许多产生结果的可能需要在具体题目下得到满足某个条件的解。
如何得到呢
我们就需要根据这个具体问题建立一个状态表dp 表在这张 dp 表中的每一个位置的数据都有明确的、相同的定义称为 状态表示而储存的每个数据就是由原问题产生的每一个子问题的解。
子问题的解又该怎么得到呢
这就需要通过对子问题如何推导状态的转移过程进行具体分析要求是每个解都能由前一个解得到从而得到所有的子问题的解。根据得到的解把 dp 表填满最后就能在这张 dp 表中找到我们要的具体答案。
梳理一下
五个思考步骤 和 注意事项
状态表示自定义一下 dp 表里的每个数据子问题的解有什么统一的含义就是 dp[i] 是什么 dp 表可能是一维数组、二维数组…需要具体分析进行选择这里的含义需要我们根据题目和经验得出这里就给大家一个分享一个经验你可以试着把 i 位置定义成 “以 i 位置为结尾 / 为开头的 xxxx” 状态转移方程一个通用公式可以用 最近一步 已知状态推出下一个状态最终达到填满 dp 表的所有状态即得到所有子问题的解初始化保证填表时不越界根据状态转移方程看哪里有越界的可能再决定怎么初始化填表顺序为了填表时所需要的状态是已知的返回值题目要求 状态表示
技巧
如果 dp[i] 有例如 “选 / 不选” 两种或多种状态那么建立两个或多个dp表也可以把几个表写成二维数组巧妙利用数组元素和数组下标尤其是对于 “无序 重复” 数据可用 eg下标对应原数据元素对应出现个数 / 总合…见题 1.5 画出每种状态的转移方程状态机对照图去写 dp 转移方程会更加清楚不容易出错。初始化 多加一位数 / 一行 / 一列 此种情况需要注意对原数组访问的时候下标还需要多减一位 如果原数组是字符串可以对原数组加一个虚拟位置见题1.4如下 str - str;为越界的位置增加一个 if() 判断会稍微改变一点 dp 转移方程的结构对于用最大或最小值初始化时会有一个计算后溢出的问题强烈建议使用这个数据 ±0x3f3f3f3fint 最大值的一半 对于 “环形xx” 想办法转成普通线性关系会简单很多
优化思路
滚动数组只留下所需状态求下一个状态滚动进行。需要注意的是滚动复制的顺序不能被覆盖。 ps:此种优化对于算法本身不是很重要可以作为了解。涉及到类似字典搜索考虑插入后用 hash 表搜索。见题 1.4 1. 子数组系列 分析状态时的通用方法
分成 自身、自身之前一个元素 进行具体考虑如果题目和数字有关分成 0、0 进行考虑 1.1 乘积为正数的最长子数组长度
详解点击 给你一个整数数组 nums 请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积为正数的最长子数组长度。 1.2 等差数列划分
详解点击 如果一个数列 至少有三个元素 并且任意两个相邻元素之差相同则称该数列为等差数列。例如[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 nums 返回数组 nums 中所有为等差数组的子数组个数。 子数组是数组中的一个连续序列。 1.3 最长湍流子数组
详解点击 给定一个整数数组 arr 返回 arr 的 最大湍流子数组的长度 。 如果比较符号在子数组中的每个相邻元素对之间翻转则该子数组是 湍流子数组 。 ps: 就是元素两两之间的增长情况是 ↗↘↗↘↗… 这样 1.4 单词拆分
详解点击 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 1.5 环绕字符串中的子字符串
详解点击 定义字符串 base 为一个 “abcdefghijklmnopqrstuvwxyz” 无限环绕的字符串所以 base 看起来是这样的 “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”. 给你一个字符串 s 请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。
