长春网站建设案例,网站维护费用明细,郑州市网站空间服务公司,三只羊网络科技有限公司T1:一个数组 中的最长 升序 子序列 的长度
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组…T1:一个数组 中的最长 升序 子序列 的长度
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解
1.关键
1这是一个 非常经典的 动态规划的 题目 就是 智工学院的上课的 那个例题
(2)利用 一个 数组 len[i] 记录 原来vec中以vec[i] 元素 作为结束的 子序列的长度
(3)从前往后更新 初始条件 len[0] 1;在计算len[i] 的时候 遍历一次 nums[0]到nums[i-1]如果有nums[j] nums[i] 那个 max的长度 可以是 len[j]1,实在没有就设置为1
2.代码
class Solution {
public:int lengthOfLIS(vectorint nums) {//找出 最长的严格上升 子序列的 长度 //利用 动态规划的 转移方程只要遍历依次即可//len[i]代表 以nums数组中第i个元素结束的 所有子序列中 最长的长度//转移方程 len[0]-len[i-1]中的如果有nums[0]-nums[i-1] nums[i]的最长的1//实在没有就设置为1 这个就是 递推关系 方程转移方程int size nums.size();vectorint len(size,0);len[0] 1;for(int i1;isize;i){//--int max 1;for(int j0;ji-1;j){if(nums[j] nums[i]){int tmp len[j];if(len[j] 1 max){max len[j]1;}}}len[i] max;}//--遍历依次 len数组即可int max len[0];for(int i1;isize;i){if(len[i] max){max len[i];}}return max;}
};
T2:上一题的 拓展最长 递增子序列的 个数
给定一个未排序的整数数组 nums 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
解
1.关键
1上一问 利用的是vectorint len用len[i]来存储 以对应 位置元素作为结尾的 递增子序列的 最大长度
2这里考虑 使用 vectorpairint,int len, len[i].first 用来存储以第i个元素作为结尾的 递增子序列的最大长度 len[i].second用来存储 这样的 子序列的 个数
(3 最重要的 就是 转移方程中 是cntlen[j].second 或者 cnt len[j].second 不是1
2.代码
class Solution {
public:int findNumberOfLIS(vectorint nums) {//没有区别反正就是最后 遍历的那一步改一下即可int size nums.size();vectorpairint,int len(size,make_pair(0,0));len[0] make_pair(1,1); //以第0个元素结尾的递增子序列最大长度为1且这种序列有1个int max_all 1;for(int i1;isize;i){int max1;int time 1; //max出现的次数//int max_add 0;for(int j0;ji-1;j){if(nums[j] nums[i]){//进入这里说明 len[i]2//虽然可能max max_all 但是这个结尾可能有 多个if(len[j].first 1 max){timelen[j].second; //加上 第j个下标为止的 出现次数}else if(len[j].first1 max){max len[j].first1;timelen[j].second; //重新计数}}}len[i] make_pair(max,time); //这个是 以nums[i]结尾的 最长的子序列的长度 和 出现的次数if(max max_all){//cout竟然没来过》endl;max_all max;}}//特殊if(max_all 1){//cout来过吗endl;return size; //所有都是}//遍历一次int ans 0;for(auto [v1,time1]:len){if(v1 max_all){anstime1;}}return ans;//悟原来 可能会有可能是 相同的 终点//所以 不用len数组进行记录 终点 而是 记录当前遍历过的 长度为 “当前max”的子序列个数//遍历len数组}
};
T3俄罗斯套娃 信封问题
给你一个二维整数数组 envelopes 其中 envelopes[i] [wi, hi] 表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候这个信封就可以放进另一个信封里如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封即可以把一个信封放到另一个信封里面。
注意不允许旋转信封。
解
法一考虑使用 归并排序以第一个数据的大小为基准 一般的 最大递增子序列
1.关键
1熟练递归函数的写法merge_sort函数是一个递归函数一直递归到 只有0个或者1个元素为止,然后递归调用merge_sort,最后将有序的left 和 right 传递给merge返回一个排序好的 、 merge函数是一个普通的迭代函数通过把 2个有序的线性表 left 和 right 合并为一个有序的 线性表 ans即可
(2)最大递增子序列的 写法见上
2.代码
class Solution {
public:int maxEnvelopes(vectorvectorint envelopes) {//这个题目 和 最大递增子序列 如出一辙,几乎没有区别//(1)算了 先写一个 归并排序好了就按照第一个 元素的大小 进行排序merge_sort(envelopes);//好吧。当我没说 应为这一题需要考虑顺序 所以可以先排序int max_all 1;int size envelopes.size();vectorint len(size,0);len[0] 1;for(int i1;isize;i){int max 1;for(int j0;ji-1;j){if(envelopes[j][0] envelopes[i][0] envelopes[j][1] envelopes[i][1]){//可以加1了if(len[j] 1 max){max len[j] 1;}}}len[i] max;if(max max_all){max_all max;}}//show(len);return max_all;}//--merge_sort函数void merge_sort(vectorvectorint envelopes){//这是一个递归函数先不断分成 1个元素 或者 0 个元素然后将 有序的 left 和 right传给//merge函数进行合并int size envelopes.size();//(1)出口if(size 0 || size 1){return ;}//(2)先 一直二分 到 只剩1个或者 0个元素为止int size_left size/2;int size_right size-size_left; //右边数组的 大小vectorvectorint left(envelopes.begin(),envelopes.begin()size_left); //应该是 左闭右开--测试一下 √vectorvectorint right(envelopes.begin()size_left,envelopes.end());//(3)分别对 left 和 right调用2次 merge_sortmerge_sort(left);merge_sort(right);//(4)现在得到的 left 和 right都是 有序的了//可以merge了envelopes merge(left,right);}vectorvectorint merge(vectorvectorint left,vectorvectorint right){//(1)左右 2个数组都是有序的int size1 left.size();int size2 right.size();if(size1 0){return right;}if(size2 0){return left;}//(2)进行循环 合并int i0, j0;vectorvectorint ans;while(isize1 j size2){//让第一个元素 小的 先加入到 ans中if(left[i][0] right[j][0]){ans.push_back(left[i]);i;}else {ans.push_back(right[j]);j;}}//(3)收尾while(isize1){ans.push_back(left[i]);}while(jsize2){ans.push_back(right[j]);}return ans; //这是一个 合并好的 有序 数组}
};可惜 这种方式有2个测试用例超时了只能 另谋出路
法二二分 -- 这里抄答案了。。。
class Solution {
private:struct node {int w, h;node(): w(0), h(0) {}node(int x, int y): w(x), h(y) {}};
public:int maxEnvelopes(vectorvectorint envelopes) {int lenenvelopes.size();if(len0) return 0;vectornode arr;for(auto a:envelopes) arr.push_back(node(a[0],a[1]));sort(arr.begin(), arr.end(), [](node x, node y){return x.wy.w || (x.wy.w x.hy.h);});vectorint res(1,arr[0].h);int j0;for(int i1; ilen; i) {if(arr[i].hres.back()) res.push_back(arr[i].h);else {jlower_bound(res.begin(), res.end(), arr[i].h, greaterint())-res.begin();res[j]arr[i].h;}}return res.size();}
};
T4:最大 连续 子序列的和
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。
解
1.关键
1递推关系 dp[i] max(dp[i-1] nums[i] , nums[i] ) 初值 dp[0] nums[0]
2.代码
class Solution {
public:int maxSubArray(vectorint nums) {//连续的 最大子序 和 //递推关系dp[i] max(dp[i-1] , dp[i-1] nums[i])//初值dp[0] nums[0]int size nums.size();vectorint dp(size,0);dp[0] nums[0];int max_num dp[0];for(int i1;isize;i){dp[i] max(nums[i], dp[i-1] nums[i]);if(dp[i] max_num){max_num dp[i];}}return max_num;}
};
T5:乘积最大 连续子数组
给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
解
1.关键
1虽然思路 和 上面这个求和的题目是一样的但是 要考虑 “负数”的影响
(2)创新想法考虑使用dp1[i] 存储以第i个元素结束的最大连续乘积 使用dp2[2]存储以第i个元素结束的最小连续乘积
(3)修改后的 递推关系状态转移方程:
dp1[i] max(nums[i],nums[i]*dp1[i-1] ,nums[i]*dp2[i-1]); // dp2[i] min(nums[i],nums[i]*dp1[i-1],nums[i]*dp2[i-1]);
2.代码
class Solution {
public:int maxProduct(vectorint nums) {//哎先尝试一下是否可以利用 “求和”一样的想法//果然不行因为你想可能dp[i-2] 0 ,但是 nums[i-1] 0 而nums[i] 0//建议保留 最大数 和 最小的数我觉得可以 分别用dp1 和 dp2 两个数组进行存储//然后 dp1[i] max(nums[i],nums[i]*dp1[i-1] ,nums[i]*dp2[i-1]);// dp2[i] min(nums[i],nums[i]*dp1[i-1],nums[i]*dp2[i-1]);//最后返回 max_num1即可int max_num nums[0];int min_num nums[0];int size nums.size();vectorint dp1(size,0);vectorint dp2(size,0);dp1[0] nums[0] ; //初值dp2[0] nums[0] ;for(int i1;isize;i){dp1[i] max_3(nums[i] , dp1[i-1]*nums[i],dp2[i-1]*nums[i]);dp2[i] min_3(nums[i] , dp1[i-1]*nums[i],dp2[i-1]*nums[i]);if(dp1[i] max_num){max_num dp1[i];}}return max_num;}//--自己写2个3元max 和 3元min的函数int max_3(int a,int b, int c){if(ab ac){return a;}else if(bc){return b;}return c;}int min_3(int a,int b,int c){if(ab ac){return a;}else if(bc){return b;}return c;}
};
T6:环形连续子数组的 最大和
给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], ..., nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。
解
法一3个测试用例超时最朴素的想法以0-n-1的下标分别作为起点然后从这n中case中取出最大值即可
1.关键
1外层变量i从0到size-1,表示以第i个下标作为起点 转换到“非环形数组”的情况
(2)内层进行 % 取模运算之后就 简单了
(3)特别注意为了防止出现负数的取模运算我们格外size
2.代码:
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {//这个就是 连续子数组的 最大连续和 的环形数组变形题目//主要是 起点的问题啊int size nums.size();//最朴素的 想法就是 分size个不同的起点 进行讨论 然后其最大值//那就先按照这种想法进行求解好了//假设某一次 从起点 下标i开始int max1 nums[0];for(int i0;isize-1;i){//递增的dp[j%size] , 就可以了 ,nice//vectorint dp(size,0);dp[i%size]nums[i%size];int max2 nums[i%size]; //初值设置好然后可以进行 递推了for(int j(i1)%size; (j%size)!i%size; j){dp[j%size] max(dp[(j-1size)%size]nums[j%size] , nums[j%size]);//哦原来是这个地方“负数”进行模运算一定要转换为 整数进行模运算if(dp[j%size] max2){max2 dp[j%size];}}if(max2 max1){max1 max2;}}return max1;}
};
法二借鉴 题解的那个想法图解 很美妙-- 将 “环形数组”的连续和 分为 收尾不接 和 收尾相接
1.关键 1总共2中情况第一种就是一般的 连续子数组的最大和 第二种就是用 数组中元素的总和 -减去连续子数组的最小和
(2)不过呢有一个小坑就是求min_num最小连续子数组的和的 时候最好从下标1开始计算直接忽略下标0开始的case因为这样可以防止min_num和total_sum都取了整个数组之和反正min_num少考虑的情况在max_num中其实已经考虑过了
2.代码 class Solution {
public:int maxSubarraySumCircular(vectorint nums) {//那个 国外的题解的 图形化讲解 非常到位//环形2中case 收尾不接 和 收尾相接//而根据 图形中的描述收尾相接其实 就是 数组总和 - 收尾不接的min连续和//分别计算 min 和 max 的数组连续和int size nums.size();//特殊if(size 1){return nums[0];}vectorint dp1(size,0); //求maxvectorint dp2(size,0); //求mindp1[0] nums[0]; dp2[1] nums[1]; //设置初值int max_num nums[0];int min_num nums[1];int total_sum nums[0];for(int i1;isize;i){//(1)求总和:total_sum nums[i];//(2)递推dp1[i] max(nums[i] , nums[i] dp1[i-1]);if(dp1[i] max_num){max_num dp1[i];}if(i 1){dp2[i] min(nums[i] , nums[i] dp2[i-1]);if(dp2[i] min_num){min_num dp2[i];}}}//不能为空集对吧那简单只要 min_num连续和 是从下标1开始计算的就好了int ans max(max_num , total_sum - min_num);return ans;}
};
T7: 最大子矩阵和
给定一个正整数、负整数和 0 组成的 N × M 矩阵编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]其中 r1, c1 分别代表子矩阵左上角的行号和列号r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵返回任意一个均可。
注意本题相对书上原题稍作改动
解
第一次代码虽然有2个测试用例超时了
1.关键
1核心思想 “降维”将二维降至一维的case通过一个2层循环得到从第i行到第j行的每一列之和 作为 一维数组base数组的对应列的数值 然后对base数组用 一维最大连续子数组的方法进行求和
2.第一次代码
class Solution {
public:vectorint getMaxMatrix(vectorvectorint matrix) {//借鉴了讨论区的 思路后自己重新思考一遍//(1)核心思想“降维”--将二维的问题转化为 一维的问题//设置一个一维数组base,然后通过2层循环遍历:第i行 到第j行 中第k列之和存到base[k]中//然后 对base数组 使用 一维数组 最大子数组连续和的 思路即可//好吧还是有2给测试用例超时了应该少用一个循环的int size_i matrix.size();int size_j matrix[0].size();//特殊:int max_all matrix[0][0];vectorint ans(4,0);//vectorint base(size_j , 0);for(int i0;isize_i - 1;i){for(int ji;jsize_i - 1;j) {vectorint base(size_j , 0); //忘记置0了//从第i行到 第j行之和for(int k0;ksize_j-1;k){for(int ui;uj;u){base[k]matrix[u][k];}}//好了现在得到了base数组了,然后利用 一个子函数 得到maxvectorint index(2,0);int max_sum max_vec(base,index); //还要起点 和 终点//记录 左上角 和 右下角//左上角i,index[0] 右下角 (j,index[1])if(max_sum max_all){max_all max_sum;ans[0] i;ans[1] index[0];ans[2] j;ans[3] index[1];}}}return ans;}//--一维数组 最大连续子数组的 和int max_vec(vectorint nums ,vectorint index){//--int dp_inums[0];int max_sum nums[0];int size nums.size();int begin 0;int end 0;for(int i1;isize;i){if(dp_i nums[i] nums[i]){//自立门户dp_i nums[i];begin i;}else{dp_i nums[i] dp_i;}if(dp_i max_sum){max_sum dp_i;//记录起点 和 终点index[0] begin;index[1] i;}}return max_sum;}
};
修改后代码
class Solution {
public:vectorint getMaxMatrix(vectorvectorint matrix) {//这一波借鉴了讨论区的想法之后悟了int size_i matrix.size();int size_j matrix[0].size();int dp_i matrix[0][0];int max_all matrix[0][0];vectorint ans(4,0); //用于记录左上角 和 右下角的 坐标int left_1 0; //记录左上角int left_2 0;//3层循环for(int i0;isize_i-1;i){vectorint base(size_j,0); //初始话base数组for(int ji;jsize_i-1;j){dp_i 0;//一层的求和,从上往下进行求和for(int k0;ksize_j-1;k){base[k]matrix[j][k];//现在base就是 原来一维数组中的nums//然后 与dp_i 进行比较if(dp_i 0){//求和dp_i base[k];}else{//自立门户dp_i base[k];//记录左上角left_1 i;left_2 k;}if(dp_i max_all){//好了确定了全局最大值了max_all dp_i;ans[0] left_1;ans[1] left_2;ans[2] j;ans[3] k; }}}}return ans;}
};
!!有一点值得注意就是 在每一次探索开始时令dp_i 0这么做的 合理性在于 :之后的判断中如果dp_i 0 那么直接加 如果dp_i 0 ,就把dp_i“换掉自立门户”,OK
T8:矩阵区域 不超过k的最大和
给你一个 m x n 的矩阵 matrix 和一个整数 k 找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
解
1.关键
1这一题 在“降维”的操作上 和 上一题 如出一辙但是 在内部是先对求出整个base一维数组并没有使用dp_i进行递推
2最精妙的一步就是 利用set容器可以 求出 lower_bound(s-k)就是说找到恰好比s-k大的那个迭代器所以这个位置的最大不超多k的连续和就是 从前加到这个位置的和sum -(减去)那个迭代器的数值这里有点贪婪法的味道
3有一点值得注意就是 set容器在初始化的时候 需要向其中添加一个元素0
其实就是说有一个非常特殊的情况就是求和sum-k0的情况这时候即使set中之前没有加入一个0的元素也应该修改ansk才行所以干脆先将0加入到set中
2.代码
class Solution {
public:int maxSumSubmatrix(vectorvectorint matrix, int k) {//好了这个题目和上一题几乎一样而且更加简单--当我没说//好了借鉴了官方的题解这个题虽然 这“降维”这件事上和上一题一样//但是在计算dp_i这件事上其实并没有用到动态规划//而是利用sum求和 - lower_bound(s-k)这个转化int size_i matrix.size();int size_j matrix[0].size();int dp_i matrix[0][0];const int MAX_Int 0x6ffffff;int max_all -MAX_Int; //也可以使用limit.h中的INT_MIN//开始3层循环for(int i0;isize_i;i){vectorint base(size_j ,0);for(int ji;jsize_i;j){//先求出所有的basefor(int k0;ksize_j-1;k){base[k] matrix[j][k];}//然后 利用set容器的lower_bound操作setint sum_set; //这里必须初始加入一个0的元素int sum0; //从前往后遍历的 总和for(auto item:base){sum item;auto left_bound sum_set.lower_bound(sum-k);if(left_bound!sum_set.end()){max_all max(max_all,sum-*left_bound);}sum_set.insert(sum);}}}return max_all;}
};
T9:打家劫舍
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
解
1.关键
1和《离散数学》中那种 最长没有连续0的bit串这种问题一样 很容易反应到这是一道递推关系的问题
(2)初值dp[0] nums[0] , dp[1] nums[1] ,dp[2] nums[0] nums[2]
dp[i]的含义以nums[i]结束的最大可能的“和”
3递推关系dp[i]max(dp[i-2]nums[i] , dp[i-3]nums[i])
2.代码
class Solution {
public:int rob(vectorint nums) {//只要找到递推关系 和 初值条件就 可以 KO了//dp[i]代表 以第nums[i]为结尾的 最大和//初值:dp[0] nums[0] , dp[1] nums[1] dp[2] nums[0] nums[2]//递推关系dp[i] max(dp[i-2]nums[i] , dp[i-3]nums[i]) 隔1个 或者 隔2个的情况加以讨论int size nums.size();//特殊if(size 1){return nums[0];}if(size 2){return max(nums[0],nums[1]);}vectorint dp(size,0);dp[0] nums[0];dp[1] nums[1];dp[2] nums[0]nums[2];for(int i3;isize-1;i){dp[i] max(dp[i-2]nums[i] , dp[i-3] nums[i]); //i-3不一定成立}int ans max(dp[size-2] , dp[size-1]);return ans;}
};
T10:打家劫舍II--环形数组形式
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
解
1.关键
1size3都 只能取一个元素 所以直接 特殊考虑就好了
(2)一般情况的话建议 分2个case进行考虑第一种不取nums[size-1] 第二种 不取nums[0]
然后 return max(max1,max2)
2.代码
class Solution {
public:int rob(vectorint nums) {//(1)size3都算特殊情况处理//(2)收尾只取一个的时候就和上一题一样了//--int size nums.size();if(size 1){return nums[0];}else if(size 2){return max(nums[0] , nums[1]);}else if(size 3){//依然只能3取1int tmp max(nums[0],nums[1]);return max(tmp,nums[2]);}//初值://--不取nums[size-1]vectorint dp(size,0);dp[0] nums[0];dp[1] nums[1];dp[2] nums[0] nums[2];for(int i3;isize-2;i){dp[i] max(dp[i-2]nums[i] , dp[i-3]nums[i]);}int max1 max(dp[size-2],dp[size-3]);//--不取nums[0]vectorint dp2(size,0);dp[0] nums[1];dp[1] nums[2];dp[2] nums[1] nums[3];for(int i3;isize-2;i){dp[i] max(dp[i-2]nums[i1],dp[i-3]nums[i1]);}int max2 max(dp[size-2],dp[size-3]);return max(max1,max2);}
};
T11:删除 与 获得 点数 打家劫舍的 变形
给你一个整数数组 nums 你可以对它进行一些操作。
每次操作中选择任意一个 nums[i] 删除它并获得 nums[i] 的点数。之后你必须删除 所有 等于 nums[i] - 1 和 nums[i] 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
解
1.关键
1先对nums数组进行排序变成递增的数组
(2)利用一个map1 记录val,time 每种元素出现的次数
(3)为了方便处理将map1转移到 vecpairval,time 中
(4)map1.size() size2 , 特殊size2 1 或者 size2 2 可以直接处理
(5)vectorint dp(size2,0) ,注意这里有一个skill就是让dp从-1开始用等价于 dp[0] 0;含义就是 dp[i] 对应以第i-1个元素作为结尾的 最大抢劫数目这样初值条件 dp[0] ,dp[1] ,dp[2]比较好求一些
(6)递推方程 分2种情况考虑:
case1 : vec[i].first 和 前一个是邻居
case2:vec[i].first 和 前一个不是邻居 , 然后可以比较方便的写出递推方程
2.代码
class Solution {
public:int deleteAndEarn(vectorint nums) {//先排序 然后就是有 重复的 “打家劫舍”问题妙啊//只要将 一次打劫一家 改为 打劫所有nums[i]相同的家庭 即可//(1)排序sort(nums.begin(),nums.end());//(2)打家劫舍int size nums.size();//特殊:if(size 1){return nums[0];}//递推关系//我认为 可以 用一个map存储然后//dp[i] max(nums[i] dp[i-2] , nums[i] dp[i-3]);//map不好访问不如利用 一个大小为size的 vecpairval,time 的辅助数组进行存储//利用快慢指针转移到这个辅助数组中//不如先用 map存一遍 然后再转移到一个vec中mapint,int map1; //val,timefor(auto item:nums){map1[item];}int size2 map1.size();vectorpairint,int vec(size2 , make_pair(0,0));int i0;for(auto [val,time]:map1){vec[i].first val;vec[i].second time;i;}//3利用vec容器来写转移方程//特殊:if(size2 1){return vec[0].first * vec[0].second;}else if(size2 2){if(abs(vec[0].first - vec[1].first) 1){return max(vec[0].first * vec[0].second , vec[1].first * vec[1].second);}else{return vec[0].first * vec[0].second vec[1].first * vec[1].second;}}//--?? 3个元素的case先pass//只有当前3个元素都是 递增1时才需要dp[3]这个值//算了dp从-1开始好了//测试[2,2,3,3,3,4] ,size2 3vectorint dp(size21,0);dp[0] 0;dp[1] vec[0].first * vec[0].second; //dp[1] 2*2 4if(abs(vec[0].first - vec[1].first) 1){dp[2] vec[1].first * vec[1].second; //dp[2] 3*3 9}else{dp[2] vec[0].first * vec[0].second vec[1].first * vec[1].second;}//考虑使用一个dp[-1]0 作为一个初值条件for(int i3;isize2;i){//分情况 递推:if(vec[i-1].first - vec[i-2].first 1) //vec[0-2]可用{//好了它们是邻居dp[i] max(vec[i-1].first*vec[i-1].second dp[i-2] ,vec[i-1].first*vec[i-1].second dp[i-3]); //得到dp[3] max(44 , 4 0) 8}else{//不是邻居dp[i] max(vec[i-1].first*vec[i-1].second dp[i-1] ,vec[i-1].first*vec[i-1].second dp[i-2]);}}return max(dp[size2-1],dp[size2]);}
};
T12:3n块披萨
给你一个披萨它由 3n 块不同大小的部分组成现在你和你的朋友们需要按照如下规则来分披萨
你挑选 任意 一块披萨。 Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。 Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。 重复上述过程直到没有披萨剩下。 每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
解
1.关键
1问题转化这一题 等价与 从3n个数字中 选择 n个 不相邻的 数字之和 最大
可以反证只要选了相邻的2个数字一定不符合要求
(2)dp[i][j] 二维递推数组 含义从前i个从1开始用元素中选择j个不相邻的数值的 最大和
3利用dp[0][0] 0 可以等价于 设置了一个 -1位置的 初值条件
(4)递推关系 dp[i][j] max(dp[i-1][j] , dp[i-2][j-1]slices[i-1]) 结合上述含义 很容易 分析出 这个递推关系的含义
2.代码
class Solution {
public:int maxSizeSlices(vectorint slices) {//有点像环形 “打家劫舍” 但又 不完全是//给一个长度为 3n的环形数组其中选择n个不相邻的 数之和 使得它们的和最大//原来使利用的 二维dp[i][j],含义从前i个元素中 选择j个元素之和的最大值//这里和 那个打家劫舍II的思路一样考虑分取slices[0] 和 取slices[size-1]2中casevectorint vec1(slices.begin()1,slices.end());vectorint vec2(slices.begin() , slices.end()-1);int ans1 max_cnt(vec1);int ans2 max_cnt(vec2);return max(ans1,ans2);}int max_cnt(vectorint slices){//返回最大值int size slices.size(); //因为相比于 原来的数组少了一个元素 int choose_cnt (1size)/3; //需要选择的最大元素个数 , 也要预留一个-1位置作为一个也不选为0//注意dp使有一个等价-1位置可以用的那个位置的元素为0vectorvectorint dp(size1 ,vectorint(choose_cnt1,0));//方正i 和 j 都是从1开始用表示 第i个元素for(int i1;isize;i){for(int j1;jchoose_cnt;j){//递推关系dp[i][j] max(dp[i-1][j] , (i-20 ?dp[i-2][j-1] : 0) slices[i-1]); //从前i-1个中 选取 j个元素 或者从前i-2个中选j-1个 slice[i-1]//这里巧妙的利用了i-20 ? dp[i-2][j-1]:0 单独考虑了 第1个元素的情况!!!}}return dp[size][choose_cnt];}
};
T13:最长的 斐波那契子序列的 长度
如果序列 X_1, X_2, ..., X_n 满足下列条件就说它是 斐波那契式 的
n 3 对于所有 i 2 n都有 X_i X_{i1} X_{i2} 给定一个严格递增的正整数数组形成序列 arr 找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在返回 0 。
回想一下子序列是从原序列 arr 中派生出来的它从 arr 中删掉任意数量的元素也可以不删而不改变其余元素的顺序。例如 [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列 解
1法一虽然只通过了29个测试用例然后就超时了
1.关键
1利用一个 二维数组 dp[i][j] 作为 递推数组 含义以第j个元素作为倒数第二个元素 以第i个元素作为最后一个元素的 最长斐波那契子序列的 长度
(2)递推关系 :分情况讨论 kfind_it(i,j,arr) ,代表 前面可以连接的元素 下标位置如果k-1,说明不能连接 将dp[i][j] 设置为2虽然这个2没有什么意义
如果k!-1 ,那么考虑使 以第k个元素开始 “自立门户 ”得到dp[i][j] 3
还是 直接连接到k的上一次 如果find_it(j,k,arr) ! -1 可以连接 dp[i][j] dp[j][k]2;
(3)其中arr是一个严格递增的有序数组查找函数find_it使用的使 二分搜索
2.代码
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {//条件中 有提到 元素使 严格递增互异的//dp[i][j] 以第j个元素 第i个 元素 结尾 的 最长斐波那契子序列// j i//从第0-j-1个元素中 找到 符合arr[i] - arr[j] 的大小的元素 arr[k]//然后 dp[i][j] dp[k][m]2(其中dp[k][m]中找到最大的那个元素即可)// 或者 dp[i][j] vec[k] ,vec[k] max(dp[k][m]) , 0mk-1//利用 二分查找 dp[k][m]中的最大值//利用 二分查找 arr[0-j-1]中是否有符合条件的值arr[k]//干脆用一个 一维数组 vec[k] 存储以第k个元素结尾的最长的斐波那契子序列int size arr.size();vectorvectorint dp(size,vectorint(size,0));//i0 的那一行不用 1i size-1 , 0j i-1//(1)初始条件//vec[0] 1//先算 dp[1][0] -- 从而得到 vec[1]2//再算 dp[2][0] 和 dp[2][1] -- 从而得到 vec[2] xxx (3)//再算 dp[3][0] 和 dp[3][1] 和 dp[3][2] -- 从而得到 vec[3] xxx(4)vectorint vec(size,0);vec[0] 1;vec[1] 2;int max_all 2;//(2)从dp[2][j]开始递推//感觉dp[i][0]都应该 2for(int i1;isize-1;i){dp[i][0] 2;}for(int i2;isize-1;i){int max_len 2;for(int j1;ji-1;j){//二分查找是否有 符合 arr[k] arr[i] - arr[j] 的这个第k个元素int k find_it(i,j,arr);if(k -1){//没有以 j ,i 结尾的子序列dp[i][j] 2; //长度设置为2好了}else{//dp[i][j] dp[j][k] 2;if(find_it(j,k,arr)! -1){dp[i][j] dp[j][k]1;}else{dp[i][j] 12;}//这么干还是不妥因为 3,11,14只能构成3 但是我弄成了4//核心问题到底13这一对可以加入与否//其实 我写的这些 都存在一个致命的问题就是 找到以j,i结尾了//但是就是找到了k那你怎么直到j和k也可以//除非 dp[i][j] dp[j][k]2;//现在还剩下1个问题就是第1个元素和第二个元素//有办法了直接将dp[j][k] 2的时候单独处理//从0-k-1中去找是否有 arr[j] - arr[k]的值//又是二分查找if(dp[i][j] max_len){max_len dp[i][j]; //得到最大的长度最后赋值 给 vec[i]}}}//遍历查找dp[i][所有j] ,得到max 给到vec[i]//vec[i] max_len;//cout以arr[i]结尾的最大长度:max_lenendl;if(vec[i] max_all){max_all vec[i];}}//从所有的vec[i]中找到最大的if(max_all 2){return 0;}return max_all;}//--二分查找目标函数:int find_it(int i, int j ,vectorint arr){int k -1; //默认k-1表示没有找到 , 其中 0k j-1int target arr[i] - arr[j];//利用二分查找ij-1; j 0;while(i j){int mid (ij)/2;if(arr[mid] target){return mid;}else if(arr[mid] target){//i 太大了i mid-1;}else if(arr[mid] target){//j 太小了j mid1;}}return -1;}
};
法二借鉴讨论区的 思想,利用一个map容器进行改进
1.关键
1利用map1存储 从arr[i]数值 映射到 i 下标
(2)利用map2存储“路径”最终以j-k结束的 最大长度 虽然有2个长度还没加上注意这里没有用pair而是用的skill:j*sizek 来“唯一”的表示一个坐标点
(3)递推关系:
if(arr[k] - arr[j] arr[j] map1.count(arr[k]-arr[j])) //说明这个 下标为i的点使存在的
map2[j*sizek] map2[i*sizej] 1;
4这里附带 讨论区的思路
思路
将斐波那契式的子序列中的两个连续项 A[i], A[j] 视为单个结点 (i, j)整个子序列是这些连续结点之间的路径。
例如对于斐波那契式的子序列 (A[1] 2, A[2] 3, A[4] 5, A[7] 8, A[10] 13)结点之间的路径为 (1, 2) - (2, 4) - (4, 7) - (7, 10)。
这样做的动机是只有当 A[i] A[j] A[k] 时两结点 (i, j) 和 (j, k) 才是连通的我们需要这些信息才能知道这一连通。现在我们得到一个类似于 最长上升子序列 的问题。
算法
设 longest[i, j] 是结束在 [i, j] 的最长路径。那么 如果 (i, j) 和 (j, k) 是连通的 longest[j, k] longest[i, j] 1。
由于 i 由 A.index(A[k] - A[j]) 唯一确定所以这是有效的我们在 i 潜在时检查每组 j k并相应地更新 longest[j, k]。 2.代码
class Solution {
public:int lenLongestFibSubseq(vectorint arr) {//悟了借鉴讨论区的方法//(1)先将 利用一个map存储用数值 - 映射到 下标iint size arr.size();unordered_mapint,int map1;for(int i0;isize-1;i){map1[arr[i]] i;}int ans0;unordered_mapint,int map2;//(2)利用另一个map2存储以j-k作为结束点 的最长序列 长度for(int k0;ksize;k){for(int j0;jk;j){//递推关系if(arr[k] - arr[j] arr[j] map1.count(arr[k]-arr[j])){//这个元素存在://这个元素的下标为iint i map1[arr[k] - arr[j]];map2[j*sizek] map2[i*size j]1;//原来以i-j为结束带你//现在长度加1//最后 总长度还要加2因为最后2个点没有计算ans max(ans,map2[j*sizek]2);}}}if(ans2){return 0;}return ans;}
};
T14:最长 等差数列
给你一个整数数组 nums返回 nums 中最长等差子序列的长度。
回想一下nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] 且 0 i1 i2 ... ik nums.length - 1。并且如果 seq[i1] - seq[i]( 0 i seq.length - 1) 的值都相同那么序列 seq 是等差的
解
法一这一题 和 上一题的 差别 主要体现在 元素可以重复所以 我打算修改上一题的 map1int ,vectorint 用一个vector数组存储所有的 具有这个val值的 下标从小到达开始存储
这是一个含有 调试代码的 代码 通过了36个测试用例后 超时了可惜
class Solution {
public:int longestArithSeqLength(vectorint nums) {//不是递增数组 而且元素之间 也不一定使 互异的//不一定使 递增的等差序列 递减的等差序列也可以//我觉得 这一题 和 上一题 几乎是一样的 因为只要确定了 j-k这个终点最表差值也就唯一确定了//现在唯一需要考虑的问题使元素是否会重复 答会所以上一题的 模板用不了 啊啊//那就修改一下从所有重复的中 找到那个可以接上 而且最大的 那个 接上//不知道mapint,vectorint 能不能用这样可以就可以 将一个val映射到 一组下标位置了//然后去找的 时候 一直找到j-1为止//开始套用上一题的 模板unordered_mapint,vectorint map1;int size nums.size();for(int i0;isize-1;i){map1[nums[i]].push_back(i); // 存入一组下标值}unordered_mapint,int map2; //用于存储以下标j-k结束的最长子序列int ans0;//--for(int k0;ksize-1;k){for(int j0;jk-1;j){//递推//(1)先看map1中有没有 int diff nums[k] - nums[j];int num_i nums[j] - diff;if(map1.count(num_i)){//(2)从这个数组中找 下标 j-1的然后从中选出map2[i*sizej]最大的,打擂台vectorint tmp map1[num_i];int size_tmp tmp.size();int max_index -1;int max_len 0;for(int i0;isize_tmp-1;i){coutdiff diffendl;coutnum_i num_iendl;coutj-k tmp[i] tmp[i]endl;if(tmp[i] j-1){break;//没有比j-1小的了跳出}if(map2[tmp[i]*sizej] max_len){//cout来过吗endl; -- 没有max_len map2[tmp[i]*sizej];max_index tmp[i];}}//说明max_index从来没有被更新过//case1: max_index -1if(max_index -1){//没有合适的}else{//cout来过吗endl; -- 没有map2[j*sizek] max_len 1;ans max(ans , map2[j*sizek] 2);}}}}if(ans 2){return 2;}else{return ans;}}
};
法二借鉴讨论区的 思路:
1.关键
1依然使 用一个map映射 从val 到 index 但是 妙 每次都只存最后一次出现的 index这一定可以保证 “最优”
2利用一个二维数组 dp[i][j] 表示 以i-j结尾的 最大长度
2.代码
class Solution {
public:int longestArithSeqLength(vectorint nums) {int n nums.size();unordered_mapint , int mp;vectorvectorint dp(n , vectorint(n , 2)); //二维 递推数组初始长度都为2int ans 0;for(int i 0 ; i n ; i){for(int j i 1 ; j n ; j){int target 2 * nums[i] - nums[j]; //从i 到 j的路径if(mp.count(target)) dp[i][j] dp[mp[target]][i] 1; //递推方程ans max(ans , dp[i][j]);}mp[nums[i]] i; //这里每次取最后一个出现的 val的 index 妙啊}return ans;}
};
T15:形成字符串的 最短路径
对于任何字符串我们可以通过删除其中一些字符也可能不删除来构造该字符串的 子序列 。(例如“ace” 是 “abcde” 的子序列而 “aec” 不是)。
给定源字符串 source 和目标字符串 target返回 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。如果无法通过串联源字符串中的子序列来构造目标字符串则返回 -1。
解
1.关键
1好吧我承认这一题 直接用 贪心的思想 就可以 得到 最优解
(2)和动态规划无关从头开始尽可能的 让source起到更多的作用 (贪心)
这么做的合理性 因为可以使用“子序列” 所以任何其它“非贪心”的选择 一定 可以组合成贪心的选择所以一定不存在 比贪心更少的 步数。
比如说source abcb target abcbaba
贪心的第一次 :可以取abc 那就取abc好了 ,下一个取的就是b了
非贪心第一次我偏不我就只取ab ,下一个我可以取cb但是这么看的话虽然看上去第二次多取了一些但之所以会这样就是因为“贪心的取法不需要在第二步取这么多了它其实也有取cb的能力但是第一步帮它分担了一个c就不需要再取c了”
这么看的结果是贪心一定不会比非贪心步数更多
2.代码
class Solution {
public:int shortestWay(string source, string target) {//既然有人用 贪心算法 解出来了那我也用 贪心好了int size1 source.size();int size2 target.size();int ans 0 ; //步数int cur1 0;int cur2 0;int flag true;while(cur2 size2){flagtrue;cur1 0;while(cur1 size1){if(source[cur1] target[cur2]){cur2;flag false; //说明cur2有移动}cur1;}if(flag true){break;}ans;}return flag?-1:ans;}
};
T16:最大 整除子集
给你一个由 无重复 正整数组成的集合 nums 请你找出并返回其中最大的整除子集 answer 子集中每一元素对 (answer[i], answer[j]) 都应当满足 answer[i] % answer[j] 0 或 answer[j] % answer[i] 0 如果存在多个有效解子集返回其中任何一个均可。
解
1.关键
1集合 --子集 -- 那必然先sort排序啊
(2)最朴素的想法就是 把前面所有可能的值 全部遍历一次因为 “因子”这东西真的只好用遍历
(3)dp[i] 一维 递推数组 代表以第i个元素作为 结束点的 最长 整除子集的长度
dp_vec[i]代表 对应上述那个最长整除子集的 具体元素的一个集合 dp_vec是一个二维数组
2.代码
class Solution {
public:vectorint largestDivisibleSubset(vectorint nums) {//1先排序然后 就变成和 最长的 斐波那契数 那个题 有点像了sort(nums.begin() , nums.end());//(2)然后 利用2个map加以处理//利用数组进行存储://最朴素的方法就是 从后往前 遍历找因子int size nums.size();vectorint dp(size,0);vectorvectorint dp_vec(size);dp[0] 1 ; //初值dp_vec[0].push_back(nums[0]); //int max_all 1;int max_index 0;for(int i1;isize;i){int max_len 1;int from_j -1;for(int ji-1;j0;j--){if(nums[i]%nums[j] 0){if(dp[j] 1 max_len){max_len dp[j] 1;from_j j;}}}dp[i] max_len;//将dp_vec[j]这个数组加上一个nums[i]变成dp_vec[i]if(from_j -1){dp_vec[i].push_back(nums[i]);//自立门户}else{dp_vec[i] dp_vec[from_j];dp_vec[i].push_back(nums[i]);//添加新的元素}if(dp[i] max_all ){max_all dp[i];max_index i;}}return dp_vec[max_index];}
};
T17:最长有效括号
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
解
1.关键我采用的 利用一个一维数组dp记录dp[i]代表以s中第i个元素结束的最长的 有效括号长度
(1)int max_anx: 用于记录 打擂台中的所有dp[i] 的最大值
vectorint dp(n,0):用于dp[i] 记录以s中第i个元素结束的 最长有效括号 长度
(2)初值dp[0] 0
(3)重点 递推关系:
case1: s[i] (,好了不用看了dp[i] 一定是0
case2:s[i] ) :
1如果 s[i-1] ( ,dp[i] dp[i-2]2,当然如多i-20,就是2了
2否则需要看i-dp[i-1]-1这个位置中s的字符如果没有 或者 为),直接dp[i] 0
不然,dp[i] dp[i-1] dp[i-dp[i-1]-2] 2;
2.代码
class Solution {
public:int longestValidParentheses(string s) {//利用动态规划的思想进行求解:int max_ans 0; //所有dp[i]中的最大值int n s.size();vectorint dp(n,0); // 动态规划 一维dp数组,//--初值dp[0] 0//dp[i] 的含义以字符串s中第i个字符结束 的最长有效括号数的 长度for(int i1;in;i){//如果s[i] ( 左括号的话dp[i] 0 不用管if(s[i] )){//分情况讨论:if(s[i-1] (){dp[i] (i2?dp[i-2]:0) 2;}else{//看一下s[i - dp[i-1] -1 ] 是否 (//如果不是dp[i] 0//如果是dp[i] dp[i-1] dp[i-dp[i-1]-2] 2;if(i-dp[i-1] -1 0 || s[i-dp[i-1]-1]!(){dp[i] 0;}else if(i - dp[i-1] -1 0){dp[i] dp[i-1] 2;}else{dp[i] dp[i-1] dp[i-dp[i-1] -2]2;}}if(dp[i] max_ans){max_ans dp[i];}}}//--return max_ans;}
};
T18:等差数列划分:
如果一个数列 至少有三个元素 并且任意两个相邻元素之差相同则称该数列为等差数列。
例如[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。 给你一个整数数组 nums 返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
解
扩展思考--如果这个 不连续的序列中的 等差数列个数呢
答
好吧一开始我就没有考虑 连续 这个条件所以写出了这个代码
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {//计算一个数组中 等差序列的 个数cnt//采用动态规划的思想dp[i]代表 以nums[i]结束的 等差数列的 个数--不要长度//一个非常巧妙的数据结构 vectormapdiff,len dp(n1)//其实本来是没想过要用 这个map的本来想用一个set去代替好了但是//因为有一个问题就是如果diff这个 只有1对len2,那么就不能算数了所以还是用map好了int n nums.size();vectorunordered_mapint,int dp(n);int cnt 0 ; //记录等差序列的个数//初值:dp[0][0]1; //对于第一个元素而言它仅有的等差序列 就是它本身了所以存一个diff映射到长度1//递推关系://循环for(int j0;ji-1;j) --计算diff nums[i] - nums[j] --递推://dp[i][diff] dp[j][diff]1;//同时,if(dp[i][diff] 3 , cnt)//比如这个测试用例1 2 3 4for(int i1;in;i){for(int j0;ji;j){int diff nums[i] - nums[j];//dp[i][diff] dp[j][diff]1;//把自己 - 自己 单独考虑好了if(ji){dp[i][0] dp[i][0]1; }//--一般情况:else if(dp[j][diff] 0){dp[i][diff] 2; //第一次加入2个元素}else{dp[i][diff] dp[j][diff]1;}if(dp[i][diff] 3 ){cnt (dp[i][diff]-2);}}}show(dp);return cnt;}//有2个问题://第一测试的i2 的时候 diff 1 的cnt应该要等于3才对但是结果cnt2//这个问题的核心就是 自己 减 自己 0 但是只是产生1个元素//第二忘记后缀形式的情况了比如1 2 3 4中还可以取到 2 3 4 这种后缀//所以只要 cnt k,那么总共可以产生k-2中可能的等差序列//第三忘记了一个问题这个题目 需要“连续的数组”//辅助测试函数:void show(vectorunordered_mapint,int vec){int i0;for(auto map1:vec){couti :endl;for(auto [diff,cnt]:map1){//coutdiff diff cnt cnt;coutdiff - ;coutdiff;cout cnt -;coutcnt;coutendl;}}}
};
言归正传
解
法一 暴力搜索
1.关键
1子函数 is_right(nums , start,end) : 传递3个参数一个数组一个起点下标一个终点下标然后判断 从 下标start 到 end是否构成 连续的 等差数组
(2) 主函数 双层循环
2.代码通过12个测试用例后 超时)
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {//法一3重循环暴力破解:int n nums.size();int ans 0 ;for(int i0;i n-2;i){for(int ji1;j n;j){is_right(nums,i,j){ans;}}}return ans;}bool is_right(vectorint nums,int start,int end){//从下标start 到 下标end是否为一个等差序列if(end - start2) return false;for(int istart;iend-2;i){if(nums[i1]*2 ! nums[i] nums[i2]){return false;}}return true;}
};
法二 滑动窗口的思想
1.关键
1首先下标i从0 到n-3作为外层 循环
(2)然后计算2个元素 开头的差值diff nums[i1] - nums[i]
3最后内层循环中j从i1 到n-2,如果nums[j1] - nums[j] ! diff 可以直接break掉这个内层循环了否则ans
2.代码:
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {//滑动窗口的思想:只要后面遇到一个地方的 nums[j1] - nums[j] ! diff//直接break这个 内层循环 否则ansint ans 0 ;int n nums.size();for(int i0;in-3;i){int diff nums[i1] - nums[i];for(int ji1;jn-2;j){if(nums[j1] - nums[j] !diff){break;}else{ans;}}}return ans;}
};
法三动态规划--递推关系:
1.关键
1dp[i]--含义以nums数组中第i个元素 作为结束点的 最长的 连续等差序列
(2)递推关系
重点分析nums[i] 和 nums[i-1] , nums[i-2] 的关系是否 可以“续上”
2.代码
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {//动态规划//dp[i]代表以nums[i]中第i个元素结束的连续等差数组的个数int n nums.size();vectorint dp(n,0);int sum 0;for(int i 2;in-1;i){if(nums[i] nums[i-2] nums[i-1]*2){dp[i] dp[i-1] 1;}else{dp[i] 0;}sumdp[i];}return sum;}
}; 好了动态规划一的part1先到这里了接下来就是part2部分了
