怎么在百度做网站推广,页面设计美工,网站制作自己做服务器,腾讯邮箱登录入口个人主页#xff1a;敲上瘾-CSDN博客 动态规划 基础dp#xff1a;基础dp——动态规划-CSDN博客多状态dp#xff1a;多状态dp——动态规划-CSDN博客 目录
一、解题技巧
二、最大子数组和
三、乘积最大子数组
四、最长湍流子数组
五、单词拆分 一、解题技巧
区分子数组敲上瘾-CSDN博客 动态规划 基础dp基础dp——动态规划-CSDN博客多状态dp多状态dp——动态规划-CSDN博客 目录
一、解题技巧
二、最大子数组和
三、乘积最大子数组
四、最长湍流子数组
五、单词拆分 一、解题技巧
区分子数组子串与子序列
子数组子串在数列中的一段连续的元素组成的新数列中间不可间断。子序列在数列中从左往右依次挑选出元素组成的新数列或者说在数列中随意删除一些元素后剩下的元素组成的新数列。
用动态规划做子数组类的题时对于状态表示我们可以直接设
dp[i]为以i元素结尾的子数组的... ... 后面就根据具体的题目要求填写可能是子数组的和或者子数组的积等等无论如何都可以以i元素结尾的子数组为研究对象去思考问题如果解决不了就尝试增加状态但研究对象不要改变。如果还解决不了那么再考虑改变或增加研究对象。
二、最大子数组和 状态表示
如上技巧所述我们直接设状态转移方程
dp[i]表示以i位置结尾的子数组的最大和。
接下来只需要去尝试是否能写出正确的状态转移方程如果能那么状态表示就是对的。
状态转移方程
以i位置结尾的子数组我们可以分为两种
nums[i]单独构成一个子数组nums[i]和以i-1结尾的最大和子数组组合成的子数组。 那么这个以i-1结尾的最大子数组的值就是一个重复子问题我们假设在前面已经计算过了即dp[i-1]然后需要注意两种情况只能取一种。那么
dp[i] max(nums[i]dp[i-1]nums[i])
初始化
初始化的目的主要有两个
保证填表的时候不越界。保证填表的正确性。 因为这里有i-1所以如果从0开始填表可能会越界通常有两种解决方案 方法一把dp[0]初始化即dp[0]nums[0]然后从dp[1]位置开始填表即从nums[1]位置开始记录。 方法二开辟一个n1的空间nnums.size()让dp[0]0需要根据具体情况具体分析然后从dp[1]位置开始填写而dp[1]记录的是nums[0]的情况也就是错开一位进行记录所以需要注意映射关系。 这题看似方法一更简洁但对于其他题可能需要做更复杂的边界判断。所以在做动规题时更推荐使用方法二来解决边界问题。
填表顺序 从左往右。
返回值 dp表中的最大值。
代码示例
class Solution
{
public:int maxSubArray(vectorint nums){int nnums.size(),retINT_MIN;vectorint dp(n1);for(int i1;in1;i){dp[i]max(nums[i-1],nums[i-1]dp[i-1]);retmax(ret,dp[i]);} return ret;}
};
三、乘积最大子数组 状态表示
同样的我们假设状态表示为 dp[i]表示以i位置结尾的子数组的最大乘积。 那么状态转移方程dp[i]max(dp[i-1]*nums[i]nums[i])我们想一想这样对吗比如dp[i-1]*nums[i]nums[i]乘以一个最大积的子数组就是最大吗 如果nums是一个负数不就变成最小乘积了吗反之nums[i]小于0时乘以一个最小的数才能成为最大积。 所以当nums[i]小于0时我们需要知道以i-1结尾的子数组的最小积。
所以状态表示为
f[i]表示以i位置结尾的子数组的最大乘积。g[i]表示以i位置结尾的子数组的最小乘积。
状态转移方程
nums[i]0 f[i] max(f[i-1]*nums[i]nums[i])g[i] min(g[i-1]*nums[i]nums[i]) nums[i] 0: f[i] max(g[i-1]*nums[i]nums[i])g[i] min(f[i-1]*nums[i]nums[i])
或
f[i]max(nums[i],max(nums[i]*f[i-1],nums[i]*g[i-1]));g[i]min(nums[i],min(nums[i]*f[i-1],nums[i]*g[i-1]));
初始化 与上一题相同为防止越界我们给两个dp表都多开辟一个空间映射关系错开一位。 然后把两个dp表都初始化为1因为这里是乘法如果使用默认的0值那么这个结果都是0。
注dp[0]是我们为防止越界添加上的虚拟位置它的值需要使得后面的填表正确。
填表顺序 从左往右f表和g表一起填。
返回值 f表中的最大值。
代码示例
class Solution {
public:int maxProduct(vectorint nums){int nnums.size(), retINT_MIN;;vectorint f(n1,1),g(n1,1);for(int i1;in;i){f[i]max(nums[i-1],max(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));g[i]min(nums[i-1],min(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));retmax(ret,f[i]);}return ret;}
};
四、最长湍流子数组 题目的核心就一句话比较符号在子数组中的每个相邻元素对之间翻转。
然后找到满足这样的条件的最长子数组。
状态表示
假设状态表示为 dp[i]表示以i结尾的最长湍流子数组。
我们把数据的大小波动抽象成一条折线如下把示例1化为折线图 结果取该段 也就是子数组要满足前一个元素是上升趋势那么下一个元素必须是下降如果前一个元素是下降趋势那么下一个元素必须是上升。
我们在做状态转移方程中主要是考虑两种情况
nums[i]单独构成一个子数组nums[i]接到前一个元素结尾构成的子数组中。
第2种情况又需要分情况讨论
nums[i] nums[i-1]只有前面的子数组最终状态是呈现上升趋势时nums[i]才能接上。nums[i] nums[i-1]只有前面的子数组最终状态是呈现下降趋势时nums[i]才能接上。nums[i]nums[i-1]不能接入前面子数组。
所以我们需要把状态转移细分为两种状态
f[i]表示以i结尾并且最后一个元素呈上升趋势的最长湍流子数组的长度。g[i]表示以i结尾并且最后一个元素呈下降趋势的最长湍流子数组的长度。
状态转移方程
nums[i] nums[i-1] f[i]1g[i]f[i-1]1 nums[i] nums[i-1] f[i]g[i-1]1g[i]1 nums[i]nums[i-1] f[i]1g[i]1 因为任意一个子数组最小的长度都是1所以可以把两个dp表都初始化为1那么状态转移方程可简化为
nums[i] nums[i-1]g[i]f[i-1]nums[i] nums[i-1]f[i]g[i-1]
初始化 为防止越界我们给两个dp表都多开辟一个空间映射关系错开一位。 然后把两个dp表都初始化为1。
填表顺序 从左往右f表和g表同时填写。
返回值 f表和g表中的最大那个元素
代码示例
class Solution {
public:int maxTurbulenceSize(vectorint arr){int narr.size(),ret1;vectorint f(n,1),g(n,1);for(int i1;in;i){if(arr[i]arr[i-1]) g[i]f[i-1];if(arr[i]arr[i-1]) f[i]g[i-1];retmax(ret,max(f[i],g[i]));} return ret;}
};
五、单词拆分 状态表示
根据经验直接设状态表示
dp[i]表示从0到i位置结尾的字符串是否能被字典中的单词表示bool类型。
状态转移方程 因为在填写i时以前的每个子串是否能由字典表示已经知道储存在dp表中。那么我们只需要找到任意一个j0ji使得dp[j]true并且子字符串[j1i]能用字典表示那么dp[i]true否则dp[i]false。
所以状态转移方程
dp[i] (dp[i-1]s[ii]能用字典表示) || (dp[i-2]s[i-1i]能用字典表示) || ... ... ||(dp[0]s[1i]能用字典表示)
注s[i-1i]表示字符串中i-1到i这个子串。
初始化 为了让第一个字符元素也讨论进来我们创建n1的dp表并把dp[0]初始化为true。
填表顺序 从左往右
返回值 return dp[n]
代码示例
class Solution {
public:bool wordBreak(string s, vectorstring wordDict){int ns.size();unordered_setstring st(wordDict.begin(),wordDict.end());vectorbool dp(n1);dp[0]true;for(int i1;in;i){for(int j0;ji;j){if(dp[j]false) continue;if(st.count(string(s.begin()j,s.begin()i))){dp[i]true;break;}}} return dp[n];}
};
好题推荐
53. 最大子数组和918. 环形子数组的最大和152. 乘积最大子数组1567. 乘积为正数的最长子数组长度413. 等差数列划分978. 最长湍流子数组139. 单词拆分467. 环绕字符串中唯一的子字符串 非常感谢您能耐心读完这篇文章。倘若您从中有所收获还望多多支持呀
