网站建设项目设计报告,网站除了wordpress外,济南传承网络李聪,电商网站开发的主流技术子序列子串相关
单个指一个数组或字符串#xff0c;两个指两个数组或字符串。
最长上升子序列-单个
dp[i]#xff1a;以下标i为结尾的递增的最长子序列长度。
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。
class Solution {
public:int l…子序列子串相关
单个指一个数组或字符串两个指两个数组或字符串。
最长上升子序列-单个
dp[i]以下标i为结尾的递增的最长子序列长度。
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值。
class Solution {
public:int lengthOfLIS(vectorint nums) {int sznums.size();// dp[i] i结尾的最长子序列长度// dp[i]max(dp[i],dp[j]1)vectorint dp(sz,1);int res1;for(int i1;isz;i){for(int j0;ji;j){if(nums[i]nums[j])dp[i]max(dp[j]1,dp[i]);}resmax(res,dp[i]);}return res;}
};
最长上升子序列的个数-单个
最长连续上升子序列-单个
dp[i]以下标i为结尾的连续递增的子序列长度。
因为本题要求连续递增子序列所以就只要比较nums[i]与nums[i - 1]而不用去比较nums[j]与nums[i] j是在0到i之间遍历。
class Solution {
public:int findLengthOfLCIS(vectorint nums) {int sznums.size();vectorint dp(sz,1);int res1;for(int i1;isz;i){if(nums[i]nums[i-1])dp[i]dp[i-1]1;resmax(dp[i],res);}return res;}
};
最长重复连续子序列-两个
dp[i][j] 以下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复子数组长度。
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {int sz1nums1.size(),sz2nums2.size();vectorvectorint dp(sz11,vectorint(sz21));int res0;for(int i1;isz1;i){for(int j1;jsz2;j){if(nums1[i-1]nums2[j-1])dp[i][j]dp[i-1][j-1]1;resmax(res,dp[i][j]);}}return res;}
};
最长重复子序列-两个
dp[i][j]长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列。
主要就是两大情况 text1[i - 1] 与 text2[j - 1]相同text1[i - 1] 与 text2[j - 1]不相同
如果text1[i - 1] 与 text2[j - 1]相同那么找到了一个公共元素所以dp[i][j] dp[i - 1][j - 1] 1;
如果text1[i - 1] 与 text2[j - 1]不相同那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列取最大的。
即dp[i][j] max(dp[i - 1][j], dp[i][j - 1])。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int sz1text1.size(),sz2text2.size();int res0;vectorvectorint dp(sz11,vectorint(sz21));for(int i1;isz1;i){for(int j1;jsz2;j){if(text1[i-1]text2[j-1])dp[i][j]dp[i-1][j-1]1;elsedp[i][j]max(dp[i-1][j],dp[i][j-1]);resmax(res,dp[i][j]);}}return res;}
};
不相交的线-两个
直线不能相交这就是说明在字符串A中 找到一个与字符串B相同的子序列且这个子序列不能改变相对顺序只要相对顺序不改变链接相同数字的直线就不会相交。那么就和最长重复子序列一样了
最大连续子序列的和-单个
具有最大和的连续子数组。
dp[i]包括下标i以nums[i]为结尾的最大连续子序列和.
dp[i]只有两个方向可以推出来
dp[i - 1] nums[i]即nums[i]加入当前连续子序列和nums[i]即从头开始计算当前连续子序列和
dp[i] max(dp[i - 1] nums[i], nums[i]).
class Solution {
public:int maxSubArray(vectorint nums) {int sznums.size();vectorint dp(sz);dp[0]nums[0];int resnums[0];for(int i1;isz;i){dp[i]max(nums[i],dp[i-1]nums[i]);resmax(res,dp[i]);}return res;}
};
判断子序列-两个
dp[i][j] 表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度
if (s[i - 1] t[j - 1]) t中找到了一个字符在s中也出现了if (s[i - 1] ! t[j - 1]) 相当于t要删除元素继续匹配
if (s[i - 1] t[j - 1])那么dp[i][j] dp[i - 1][j - 1] 1;因为找到了一个相同的字符相同子序列长度自然要在dp[i-1][j-1]的基础上加1如果不理解在回看一下dp[i][j]的定义
if (s[i - 1] ! t[j - 1])此时相当于t要删除元素t如果把当前元素t[j - 1]删除那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了即dp[i][j] dp[i][j - 1]。
class Solution {
public:bool isSubsequence(string s, string t) {int sz1s.size(),sz2t.size();vectorvectorint dp(sz11,vectorint(sz21));for(int i1;isz1;i){for(int j1;jsz2;j){if(s[i-1]t[j-1]){dp[i][j]dp[i-1][j-1]1;}else{dp[i][j]dp[i][j-1];}}}return dp[sz1][sz2]sz1;}
};
子序列出现的个数-两个?
dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数。
回文子串的个数-单个
计算这个字符串中有多少个回文子串。
判断一个子字符串字符串下标范围[i,j]是否回文 依赖于
子字符串下标范围[i 1, j - 1] 是否是回文
所以为了明确这种递归关系dp数组是要定义成一个二维dp数组。
布尔类型的dp[i][j]表示区间范围[i,j] 注意是左闭右闭的子串是否是回文子串如果dp[i][j]为true否则为false。
当s[i]与s[j]不相等dp[i][j]一定是false。
当s[i]与s[j]相等时有如下三种情况
情况一下标i 与 j相同同一个字符例如a当然是回文子串情况二下标i 与 j相差为1例如aa也是回文子串情况三下标i 与 j相差大于1的时候例如cabac此时s[i]与s[j]已经相同了我们看i到j区间是不是回文子串就看aba是不是回文就可以了那么aba的区间就是 i1 与 j-1区间这个区间是不是回文就看dp[i 1][j - 1]是否为true。
class Solution {
public:int countSubstrings(string s) {int szs.size();int res0;vectorvectorbool dp(sz,vectorbool(sz));for(int i0;isz;i)dp[i][i]true;// 注意遍历顺序for(int isz-1;i0;i--){for(int ji;jsz;j){if(s[i]s[j]){if(j-i1) dp[i][j]true;else dp[i][j]dp[i1][j-1];}if(dp[i][j]) res;}}return res;}
};
最长回文子串-单个
class Solution {
public:string longestPalindrome(string s) {int len 0;int start 0;int sz s.size();vectorvectorbool dp(sz, vectorbool(sz));for (int i sz - 1; i 0; i--) {for (int j i; j sz; j) {if (s[i] s[j]) {if (j - i 2)dp[i][j] true;elsedp[i][j] dp[i 1][j - 1];}if (dp[i][j]) {if (j - i 1 len) {start i;len j - i 1;}}}}return s.substr(start,len);}
};
最长回文子序列-单个
dp[i][j]字符串s在[i, j]范围内最长的回文子序列的长度
如果s[i]与s[j]相同那么dp[i][j] dp[i 1][j - 1] 2;
如果s[i]与s[j]不相同说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。那么dp[i][j]一定是取最大的即dp[i][j] max(dp[i 1][j], dp[i][j - 1])。
class Solution {
public:int longestPalindromeSubseq(string s) {int szs.size();vectorvectorint dp(sz,vectorint(sz));int res1;for(int i0;isz;i)dp[i][i]1;for(int isz-1;i0;i--){for(int ji1;jsz;j){if(s[i]s[j]) dp[i][j]dp[i1][j-1]2;else dp[i][j]max(dp[i1][j],dp[i][j-1]);resmax(res,dp[i][j]);}}return res;}
};
二维动态
不同路径
不同路径II
01背包
有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值
所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i])。
如果改为滑动数组则需倒序遍历背包容量保证物品只被放进一次。
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
分割等和子集
背包的体积为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。背包中每一个元素是不可重复放入。
目标和
给定一个非负整数数组a1, a2, ..., an, 和一个目标数S。现在你有两个符号 和 -。对于数组中的任意一个整数你都可以从 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 假设加法的总和为x那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) target
x (target sum) / 2
此时问题就转化为装满容量为x的背包有几种方法。求组合类问题的公式
dp[j] dp[j - nums[i]]
完全背包
零钱兑换II 给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的组合的个数。
排列总和
给定一个由正整数组成且不存在重复数字的数组找出和为给定目标正整数的排列的个数。
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。
完全平方数
完全平方数就是物品可以无限件使用凑个正整数n就是背包问凑满这个背包最少有多少物品。
单词拆分
买卖股票
