生鲜网站怎么做,wordpress模版如何使用教程,asp网站建设实录,前端怎么做电商网站例题一 解法#xff08;动态规划#xff09;#xff1a; 算法思路#xff1a; 1. 状态表⽰#xff1a; 对于线性 dp #xff0c;我们可以⽤「经验 题⽬要求」来定义状态表⽰#xff1a; i. 以某个位置为结尾#xff0c;巴拉巴拉#xff1b; ii. 以某个位置…例题一 解法动态规划 算法思路 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以「某个位置为结尾」结合「题⽬要求」定义⼀个状态表⽰ dp[i] 表⽰以 i 位置元素为结尾的「所有⼦数组」中和的最⼤和。 2. 状态转移⽅程 dp[i] 的所有可能可以分为以下两种 i. ⼦数组的⻓度为 1 此时 dp[i] nums[i] ii. ⼦数组的⻓度⼤于 1 此时 dp[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼤值再加上 nums[i] 也就是 dp[i - 1] nums[i] 。 由于我们要的是「最⼤值」因此应该是两种情况下的最⼤值因此可得转移⽅程 dp[i] max(nums[i], dp[i - 1] nums[i]) 。 3. 初始化 可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」 ii. 「下标的映射关系」。 在本题中最前⾯加上⼀个格⼦并且让 dp[0] 0 即可。 4. 填表顺序根据「状态转移⽅程」易得填表顺序为「从左往右」。 5. 返回值 状态表⽰为「以 i 为结尾的所有⼦数组」的最⼤值但是最⼤⼦数组和的结尾我们是不确定的。 因此我们需要返回整个 dp 表中的最⼤值。 例题二 解法动态规划 算法思路 本题与「最⼤⼦数组和」的区别在于考虑问题的时候不仅要分析「数组内的连续区域」还要考 虑「数组⾸尾相连」的⼀部分。结果的可能情况分为以下两种 i. 结果在数组的内部包括整个数组 ii. 结果在数组⾸尾相连的⼀部分上。 其中对于第⼀种情况我们仅需按照「最⼤⼦数组和」的求法就可以得到结果记为 fmax 。 对于第⼆种情况我们可以分析⼀下 i. 如果数组⾸尾相连的⼀部分是最⼤的数组和那么数组中间就会空出来⼀部分 ii. 因为数组的总和 sum 是不变的那么中间连续的⼀部分的和⼀定是最⼩的 因此我们就可以得出⼀个结论对于第⼆种情况的最⼤和应该等于 sum - gmin 其中 gmin 表⽰数组内的「最⼩⼦数组和」。 两种情况下的最⼤值就是我们要的结果。 但是由于数组内有可能全部都是负数第⼀种情况下的结果是数组内的最⼤值是个负数第 ⼆种情况下的 gmin sum 求的得结果就会是 0 。若直接求两者的最⼤值就会是 0 。但 是实际的结果应该是数组内的最⼤值。对于这种情况我们需要特殊判断⼀下。 由于「最⼤⼦数组和」的⽅法已经讲过这⾥只提⼀下「最⼩⼦数组和」的求解过程其实与「最 ⼤⼦数组和」的求法是⼀致的。⽤ f 表⽰最⼤和 g 表⽰最⼩和。 1. 状态表⽰ g[i] 表⽰以 i 做结尾的「所有⼦数组」中和的最⼩值。 2. 状态转移⽅程 g[i] 的所有可能可以分为以下两种 i. ⼦数组的⻓度为 1 此时 g[i] nums[i] ii. ⼦数组的⻓度⼤于 1 此时 g[i] 应该等于 以 i - 1 做结尾的「所有⼦数组」中和的最⼩值再加上 nums[i] 也就是 g[i - 1] nums[i] 。 由于我们要的是最⼩⼦数组和因此应该是两种情况下的最⼩值因此可得转移⽅程 g[i] min(nums[i], g[i - 1] nums[i]) 。 3. 初始化 可以在最前⾯加上⼀个辅助结点帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要保证后续填表是正确的 ii. 下标的映射关系。 在本题中最前⾯加上⼀个格⼦并且让 g[0] 0 即可。 4. 填表顺序 根据状态转移⽅程易得填表顺序为「从左往右」。 5. 返回值 a. 先找到 f 表⾥⾯的最⼤值 - fmax b. 找到 g 表⾥⾯的最⼩值 - gmin c. 统计所有元素的和 - sum b. 返回 sum gmin ? fmax : max(fmax, sum - gmin) 。 例题三 解法动态规划 算法思路 这道题与「最⼤⼦数组和」⾮常相似我们可以效仿着定义⼀下状态表⽰以及状态转移 i. dp[i] 表⽰以 i 为结尾的所有⼦数组的最⼤乘积 ii. dp[i] max(nums[i], dp[i - 1] * nums[i]) 由于正负号的存在我们很容易就可以得到这样求 dp[i] 的值是不正确的。因为 dp[i - 1] 的信息并不能让我们得到 dp[i] 的正确值。⽐如数组 [-2, 5, -2] ⽤上述状态转移得到的 dp数组为 [-2, 5, -2] 最⼤乘积为 5 。但是实际上的最⼤乘积应该是所有数相乘结果为 20 。 究其原因就是因为我们在求 dp[2] 的时候因为 nums[2] 是⼀个负数因此我们需要的是「 i - 1 位置结尾的最⼩的乘积 -10 」这样⼀个负数乘以「最⼩值」才会得到真实的最⼤值。 因此我们不仅需要⼀个「乘积最⼤值的 dp 表」还需要⼀个「乘积最⼩值的 dp 表」。 1. 状态表⽰ f[i] 表⽰以 i 结尾的所有⼦数组的最⼤乘积 g[i] 表⽰以 i 结尾的所有⼦数组的最⼩乘积。 2. 状态转移⽅程 遍历每⼀个位置的时候我们要同步更新两个 dp 数组的值。对于 f[i] 也就是「以 i 为结尾的所有⼦数组的最⼤乘积」对于所有⼦数组可以分为下⾯三种形式 i. ⼦数组的⻓度为 1 也就是 nums[i] ii. ⼦数组的⻓度⼤于 1 但 nums[i] 0 此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i - 1] 再乘上 nums[i] 也就是 nums[i] * f[i - 1] iii. ⼦数组的⻓度⼤于 1 但 nums[i] 0 此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i - 1] 再乘上 nums[i] 也就是 nums[i] * g[i - 1] 如果 nums[i] 0 所有⼦数组的乘积均为 0 三种情况其实都包含了 综上所述 f[i] max(nums[i], max(nums[i] * f[i - 1], nums[i] * g[i - 1]) )。 对于 g[i] 也就是「以 i 为结尾的所有⼦数组的最⼩乘积」对于所有⼦数组可以分为下⾯三种形式 i. ⼦数组的⻓度为 1 也就是 nums[i] ii. ⼦数组的⻓度⼤于1 但 nums[i] 0 此时需要的是 i - 1 为结尾的所有⼦数组的最⼩乘积 g[i - 1] 再乘上 nums[i] 也就是 nums[i] * g[i - 1] iii. ⼦数组的⻓度⼤于 1 但 nums[i] 0 此时需要的是 i - 1 为结尾的所有⼦数组的最⼤乘积 f[i - 1] 再乘上 nums[i] 也就是 nums[i] * f[i - 1] 综上所述 g[i] min(nums[i], min(nums[i] * f[i - 1], nums[i] * g[i -1])) 。 如果 nums[i] 0 所有⼦数组的乘积均为 0 三种情况其实都包含了 3. 初始化 可以在最前⾯加上⼀个辅助结点帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要保证后续填表是正确的 ii. 下标的映射关系。 在本题中最前⾯加上⼀个格⼦并且让 f[0] g[0] 1 即可。 4. 填表顺序 根据状态转移⽅程易得填表顺序为「从左往右两个表⼀起填」。 5. 返回值 返回 f 表中的最⼤值。 例题四 解法动态规划 算法思路 继续效仿「最⼤⼦数组和」中的状态表⽰尝试解决这个问题。 状态表⽰ dp[i] 表⽰「所有以 i 结尾的⼦数组乘积为正数的最⻓⼦数组的⻓度」。 思考状态转移对于 i 位置上的 nums[i] 我们可以分三种情况讨论 i. 如果 nums[i] 0 那么所有以 i 为结尾的⼦数组的乘积都不可能是正数此时 dp[i] 0 ii. 如果 nums[i] 0 那么直接找到 dp[i - 1] 的值这⾥请再读⼀遍 dp[i - 1] 代表的意义并且考虑如果 dp[i - 1] 的结值是 0 的话影不影响结果然后加⼀即可此时 dp[i] dp[i - 1] 1 iii. 如果 nums[i] 0 这时候你该蛋疼了因为在现有的条件下你根本没办法得到此时的最⻓⻓度。因为乘法是存在「负负得正」的单单靠⼀个 dp[i - 1] 我们⽆法推导出 dp[i] 的值。 但是如果我们知道「以 i - 1 为结尾的所有⼦数组乘积为负数的最⻓⼦数组的⻓度」 neg[i - 1] 那么此时的 dp[i] 是不是就等于 neg[i - 1] 1 呢 通过上⾯的分析我们可以得出需要两个 dp 表才能推导出最终的结果。不仅需要⼀个「乘积 为正数的最⻓⼦数组」还需要⼀个「乘积为负数的最⻓⼦数组」。 1. 状态表⽰ f[i] 表⽰以 i 结尾的所有⼦数组中乘积为「正数」的最⻓⼦数组的⻓度 g[i] 表⽰以 i 结尾的所有⼦数组中乘积为「负数」的最⻓⼦数组的⻓度。 2. 状态转移⽅程 遍历每⼀个位置的时候我们要同步更新两个 dp 数组的值。对于 f[i] 也就是以 i 为结尾的乘积为「正数」的最⻓⼦数组根据 nums[i] 的值可以分为三种情况 i. nums[i] 0 时所有以 i 为结尾的⼦数组的乘积都不可能是正数此时 f[i] 0 ii. nums[i] 0 时那么直接找到 f[i - 1] 的值这⾥请再读⼀遍 f[i - 1] 代表的意义并且考虑如果 f[i - 1] 的结值是 0 的话影不影响结果然后加⼀即可此时 f[i] f[i - 1] 1 iii. nums[i] 0 时此时我们要看 g[i - 1] 的值这⾥请再读⼀遍 g[i - 1] 代表的意义。因为负负得正如果我们知道以 i - 1 为结尾的乘积为负数的最⻓⼦数组的⻓度加上 1 即可根据 g[i - 1] 的值⼜要分两种情况 1. g[i - 1] 0 说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是不存在的⼜因为 nums[i] 0 所以以 i 结尾的乘积为正数的最⻓⼦数组也是不存在的此时 f[i] 0 2. g[i - 1] ! 0 说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是存在的⼜因为 nums[i] 0 所以以 i 结尾的乘积为正数的最⻓⼦数组就等于 g[i - 1] 1 综上所述 nums[i] 0 时 f[i] g[i - 1] 0 ? 0 : g[i - 1] 1; 对于 g[i] 也就是以 i 为结尾的乘积为「负数」的最⻓⼦数组根据 nums[i] 的值可以分为三种情况 i. nums[i] 0 时所有以 i 为结尾的⼦数组的乘积都不可能是负数此时 g[i] 0 ii. nums[i] 0 时那么直接找到 f[i - 1] 的值这⾥请再读⼀遍 f[i - 1] 代表的意义并且考虑如果 f[i - 1] 的结值是 0 的话影不影响结果然后加⼀即可因为正数 * 负数 负数此时 g[i] f[i - 1] 1 iii. nums[i] 0 时此时我们要看 g[i - 1] 的值这⾥请再读⼀遍 g[i - 1] 代表的意义。因为正数 * 负数 负数根据 g[i - 1] 的值⼜要分两种情况 1. g[i - 1] 0 说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是不存在的⼜因为 nums[i] 0 所以以 i 结尾的乘积为负数的最⻓⼦数组也是不存在的此时 f[i] 0 2. g[i - 1] ! 0 说明以 i - 1 为结尾的乘积为负数的最⻓⼦数组是存在的⼜因为 nums[i] 0 所以以 i 结尾的乘积为正数的最⻓⼦数组就等于 g[i - 1] 1 综上所述 nums[i] 0 时 g[i] g[i - 1] 0 ? 0 : g[i - 1] 1 ; 这⾥的推导⽐较绕因为不断的出现「正数和负数」的分情况讨论我们只需根据下⾯的规则严 格找到此状态下需要的 dp 数组即可 i. 正数 * 正数 正数 ii. 负数 * 负数 正数 iii. 负数 * 正数 正数 * 负数 负数 3. 初始化 可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」 ii. 「下标的映射关系」。 在本题中最前⾯加上⼀个格⼦并且让 f[0] g[0] 0 即可。 4. 填表顺序 根据「状态转移⽅程」易得填表顺序为「从左往右两个表⼀起填」。 5. 返回值 根据「状态表⽰」我们要返回 f 表中的最⼤值。 解法动态规划 算法思路 1. 状态表⽰ 由于我们的研究对象是「⼀段连续的区间」如果我们状态表⽰定义成 [0, i] 区间内⼀共有多少等差数列那么我们在分析 dp[i] 的状态转移时会⽆从下⼿因为我们不清楚前⾯那么多的「等差数列都在什么位置」。所以说我们定义的状态表⽰必须让等差数列「有迹可循」让状态转移的时候能找到「⼤部队」。因此我们可以「固定死等差数列的结尾」定义下⾯的状态表⽰dp[i] 表⽰必须「以 i 位置的元素为结尾」的等差数列有多少种。 2. 状态转移⽅程 我们需要了解⼀下等差数列的性质如果 a b c 三个数成等差数列这时候来了⼀个 d 其中 b c d 也能构成⼀个等差数列那么 a b c d 四个数能够成等差序列吗答案是显然的。因为他们之间相邻两个元素之间的差值都是⼀样的。有了这个理解我们就可以转⽽分析我们的状态转移⽅程了。 对于dp[i] 位置的元素 nums[i] 会与前⾯的两个元素有下⾯两种情况 i. nums[i - 2], nums[i - 1], nums[i] 三个元素不能构成等差数列那么以nums[i] 为结尾的等差数列就不存在此时 dp[i] 0 ii. nums[i - 2], nums[i - 1], nums[i] 三个元素可以构成等差数列那么以nums[i - 1] 为结尾的所有等差数列后⾯填上⼀个 nums[i] 也是⼀个等差数列此时dp[i] dp[i - 1] 。但是因为 nums[i - 2], nums[i - 1], nums[i] 三者⼜能构成⼀个新的等差数列因此要在之前的基础上再添上⼀个等差数列于是 dp[i] dp[i - 1] 1 。综上所述状态转移⽅程为 当 nums[i - 2] nums[i] ! 2 * nums[i - 1] 时dp[i] 0 当 nums[i - 2] nums[i] 2 * nums[i - 1] 时 dp[i] 1 dp[i - 1] 3. 初始化 由于需要⽤到前两个位置的元素但是前两个位置的元素⼜⽆法构成等差数列因此 dp[0] dp[1] 0 。 4. 填表顺序 毫⽆疑问是「从左往右」。 5. 返回值 因为我们要的是所有的等差数列的个数因此需要返回整个 dp 表⾥⾯的元素之和。 例题五 解法动态规划 算法思路 1. 状态表⽰ 我们先尝试定义状态表⽰为 dp[i] 表⽰「以 i 位置为结尾的最⻓湍流数组的⻓度」。 但是问题来了如果状态表⽰这样定义的话以 i 位置为结尾的最⻓湍流数组的⻓度我们没法从之前的状态推导出来。因为我们不知道前⼀个最⻓湍流数组的结尾处是递增的还是递减的。因此我们需要状态表⽰能表⽰多⼀点的信息要能让我们知道这⼀个最⻓湍流数组的结尾是「递增」的还是「递减」的。因此需要两个 dp 表 f[i] 表⽰以 i 位置元素为结尾的所有⼦数组中最后呈现「上升状态」下的最⻓湍流数组的⻓度 g[i] 表⽰以 i 位置元素为结尾的所有⼦数组中最后呈现「下降状态」下的最⻓湍流数组的⻓度。 2. 状态转移⽅程 对于 i 位置的元素 arr[i] 有下⾯两种情况 i. arr[i] arr[i - 1] 如果 i 位置的元素⽐ i - 1 位置的元素⼤说明接下来应该去找 i -1 位置结尾并且 i - 1 位置元素⽐前⼀个元素⼩的序列那就是 g[i - 1] 。更新 f[i] 位置的值 f[i] g[i - 1] 1 ii. arr[i] arr[i - 1] 如果 i 位置的元素⽐ i - 1 位置的元素⼩说明接下来应该去找 i - 1 位置结尾并且 i - 1 位置元素⽐前⼀个元素⼤的序列那就是f[i - 1] 。更新 g[i] 位置的值 g[i] f[i - 1] 1 iii. arr[i] arr[i - 1] 不构成湍流数组。 3. 初始化 所有的元素「单独」都能构成⼀个湍流数组因此可以将 dp 表内所有元素初始化为 1 。由于⽤到前⾯的状态因此我们循环的时候从第⼆个位置开始即可。 4. 填表顺序 毫⽆疑问是「从左往右两个表⼀起填」。 5. 返回值 应该返回「两个 dp 表⾥⾯的最⼤值」我们可以在填表的时候顺便更新⼀个最⼤值。 例题六 解法动态规划 算法思路 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰ dp[i] 表⽰ [0, i] 区间内的字符串能否被字典中的单词拼接⽽成。 2. 状态转移⽅程 对于dp[i] 为了确定当前的字符串能否由字典⾥⾯的单词构成根据最后⼀个单词的起始位置 j 我们可以将其分解为前后两部分 i. 前⾯⼀部分[0, j - 1] 区间的字符串 ii. 后⾯⼀部分[j, i] 区间的字符串。 其中前⾯部分我们可以在 dp[j - 1] 中找到答案后⾯部分的⼦串可以在字典⾥⾯找到。因此我们得出⼀个结论当我们在从0 ~ i 枚举 j 的时候只要 dp[j - 1] true并且后⾯部分的⼦串 s.substr(j, i - j 1) 能够在字典中找到那么 dp[i] true 。 3. 初始化 可以在最前⾯加上⼀个「辅助结点」帮助我们初始化。使⽤这种技巧要注意两个点 i. 辅助结点⾥⾯的值要「保证后续填表是正确的」 ii. 「下标的映射关系」。 在本题中最前⾯加上⼀个格⼦并且让 dp[0] true 可以理解为空串能够拼接⽽成。其中为了⽅便处理下标的映射关系我们可以将字符串前⾯加上⼀个占位符 s s 这样就没有下标的映射关系的问题了同时还能处理「空串」的情况。 4. 填表顺序 显⽽易⻅填表顺序「从左往右」。 5. 返回值 由「状态表⽰」可得返回 dp[n] 位置的布尔值。 哈希表优化的⼩细节 在状态转移中我们需要判断后⾯部分的⼦串「是否在字典」之中因此会「频繁的⽤到查询操 作」。为了节省效率我们可以提前把「字典中的单词」存⼊到「哈希表」中。 例题七 解法动态规划 算法思路 1. 状态表⽰ 对于线性 dp 我们可以⽤「经验 题⽬要求」来定义状态表⽰ i. 以某个位置为结尾巴拉巴拉 ii. 以某个位置为起点巴拉巴拉。 这⾥我们选择⽐较常⽤的⽅式以某个位置为结尾结合题⽬要求定义⼀个状态表⽰dp[i] 表⽰以 i 位置的元素为结尾的所有⼦串⾥⾯有多少个在 base 中出现过。 2. 状态转移⽅程 对于dp[i] 我们可以根据⼦串的「⻓度」划分为两类 i. ⼦串的⻓度等于 1 此时这⼀个字符会出现在 base 中 ii. ⼦串的⻓度⼤于 1 如果 i 位置的字符和 i - 1 位置上的字符组合后出现在 base中的话那么 dp[i - 1] ⾥⾯的所有⼦串后⾯填上⼀个 s[i] 依旧在 base 中出现。因此 dp[i] dp[i - 1] 。 综上 dp[i] 1 dp[i - 1] 其中 dp[i - 1] 是否加上需要先做⼀下判断。 3. 初始化 可以根据「实际情况」将表⾥⾯的值都初始化为 1 。 4. 填表顺序 显⽽易⻅填表顺序「从左往右」。 5. 返回值 这⾥不能直接返回 dp 表⾥⾯的和因为会有重复的结果。在返回之前我们需要先「去重」 i. 相同字符结尾的 dp 值我们仅需保留「最⼤」的即可其余 dp 值对应的⼦串都可以在最⼤的⾥⾯找到 ii. 可以创建⼀个⼤⼩为 26 的数组统计所有字符结尾的最⼤ dp 值。最后返回「数组中所有元素的和」即可。
