目录方法论一、斐波那契数列模型1.第n个泰波那契数2.三步问题3.使用最小花费爬楼梯4.解码方法二、路径问题5.不同路径6.不同路径27.珠宝的最高价值8.下降路径最小和9.地下城游戏三、简单多状态dp10.按摩师11.打家劫舍12.打家劫舍213.删除并获得点数14.粉刷房子15.买卖股票的最佳时机含冷冻期16.买卖股票的最佳时机含手续费17.买卖股票的最佳时机三18.买卖股票的最佳时机四小知识最大最小整数的一半四、子数组系列19. 最大子数组和20环形子数组的最大和21.乘积最大子数组(最后一种情况针对用例解决解法尚有问题)22.乘积为正整数的最长子数组长度附加 跳跃游戏223.等差数列划分24.最长湍流子数组25.单词拆分26.环绕字符串中唯一的子字符串方法论1.状态表示 是什么dp表里的值所表示的含义 怎么来1.题目要求 2题目要求经验这个为主要使用方法 3分析问题过程中发现重复子问题 2.状态转移方程 dp[i]代表什么 根据最近一步的状态表示 3.初始化 保证数组不越界 4.填表顺序保证填写该状态时所需要的状态已经计算过了 5.返回值 题目要求状态表示 6.空间优化 可以使用轮换数组来减少空间消耗即使用有限个变量通过一轮轮赋值来向前推进动态规划中要弄清楚每一步是为什么多想想为什么一、斐波那契数列模型1.第n个泰波那契数1.dp[i]表示第i给泰波那契数的值题目给定 2.dp[i] dp[i-1] dp[i-2] dp[i-3] 3.将dp[0] dp[1] dp[2] 进行初始化 4.从左向右class Solution { public: int tribonacci(int n) { if(n 0)return 0; if(n 1 || n 2)return 1; vectorint dp(n1); dp[0] 0; dp[1] 1; dp[2] 1; for(int i 3; i n; i) { dp[i] dp[i-1] dp[i-2] dp[i-3]; } return dp[n]; } };2.三步问题class Solution { public: int waysToStep(int n) { if(n 2)return n; if(n 3)return 4; vectorint dp(n1); dp[1] 1; dp[2] 2; dp[3] 4; for(int i 4;i n; i) { dp[i] ((dp[i-1] dp[i-2])%(1000000007) dp[i-3])%(1000000007); } return dp[n]; } };3.使用最小花费爬楼梯1.1.dp[i]表示爬到i位置时使用的最小花费 2.dp[i] min( (dp[i-1] cost[i - 1]), (dp[i-2] cost[i - 2]) ); 3.将dp[1] dp[2] 进行初始化 4.从左向右class Solution { public: int minCostClimbingStairs(vectorint cost) { int n cost.size(); vectorint dp(n1); for(int i 2; i n; i) { dp[i] min( (dp[i-1] cost[i-1]), (dp[i-2] cost[i-2]) ); } return dp[n]; } };2.1.dp[i]表示从i位置爬到顶时使用的最小花费 2.dp[i] min(dp[i1],dp[i2])cost[i]; 3.将dp[n-1] dp[n-2] 进行初始化 4.从右向左 5.返回值是dp[0]dp[1]中小的那个class Solution { public: int minCostClimbingStairs(vectorint cost) { int n cost.size(); vectorint dp(n); dp[n - 1] cost[n - 1]; dp[n - 2] cost[n - 2]; for(int i n-3; i 0; i--) { dp[i] min(dp[i1],(dp[i2]))cost[i]; } return min(dp[0],dp[1]); } };4.解码方法class Solution { public: int numDecodings(string s) { int size s.size(); vectorint dp(size); if(s[0] 0)return 0; if(s[0] 0 s[0] 9)dp[0] 1; if(size 1)return dp[size-1]; if(s[1] 0 s[1] 9)dp[1]; int tmp (s[0]-0)*10 s[1] - 0; if(tmp 10 tmp 26)dp[1]; if(size 2)return dp[size-1]; for(int i 2; i size - 1; i) { if(s[i] 0 s[i] 9)dp[i] dp[i - 1]; tmp (s[i-1]-0)*10 s[i] - 0; if(tmp 10 tmp 26)dp[i] dp[i-2]; } return dp[size-1]; } };//使用虚拟节点优化后初始化更加方便但是需要注意映射关系 class Solution { public: int numDecodings(string s) { int size s.size(); vectorint dp(size1); dp[0] 1;//dp[0]等于1是因为在循环判断中如果s[0]能与s[1]组合它的解码方式就是一种就 //会加上dp[0] if(s[0] 0)return 0; if(s[0] 0 s[0] 9)dp[1] 1; for(int i 2; i size; i) { if(s[i - 1] 0 s[i - 1] 9)dp[i] dp[i - 1]; int tmp (s[i-1 - 1]-0)*10 s[i - 1] - 0;//映射关系改变i 要整体减1 if(tmp 10 tmp 26)dp[i] dp[i-2]; } return dp[size]; } };二、路径问题5.不同路径使用虚拟位置的方法来确定填表class Solution { public: int uniquePaths(int m, int n) { vectorvectorint dp(m1,vectorint(n1)); dp[0][1] 1;//因为[1][1]位置是初始位置初始位置就算是一种情况所以[0][1]处赋值为1 for(int i 1;i m; i) { for(int j 1;j n; j) { dp[i][j] dp[i][j-1] dp[i-1][j];//下一格的路线是接在原路线上算同一路线所 //以其路线总数就是左一格和上一格的路线之和 } } return dp[m][n]; } };6.不同路径2class Solution { public: int uniquePathsWithObstacles(vectorvectorint ob) { int m ob.size(); int n ob[0].size(); vectorvectorint dp(m1,vectorint(n1)); dp[0][1] 1; for(int i 1;i m; i) { for(int j 1;j n; j) { if(ob[i-1][j-1] 0)//主要思路同上增加障碍物的判断 dp[i][j] dp[i][j-1] dp[i-1][j]; else dp[i][j] 0; } } return dp[m][n]; } };7.珠宝的最高价值class Solution { public: int jewelleryValue(vectorvectorint fm) { int m fm.size(); int n fm[0].size(); vectorvectorint dp(m1,vectorint(n1)); for(int i 1; i m; i) { for(int j 1;j n; j) { dp[i][j] max(dp[i-1][j],dp[i][j-1])fm[i-1][j-1];//每次走之前选价值更大的 //其它同上面的题目 } } return dp[m][n]; } };8.下降路径最小和1.状态表示 下降到[i][j]的最小路径和 2.状态转移方程 前一行三个中位置的最小路径和本位置的路径长度 3.初始化 先把全部位置初始化为INT_MAX选择最小值时就不会影响到选值 把第一行初始化为0计算第一行时初始值就是该位置的路径长度 4.填表顺序 从上到下从左到右 5.返回值 最后一行最小的class Solution { public: int minFallingPathSum(vectorvectorint ma) { int m ma.size() 1; int n ma.size()2; vectorvectorint dp(m,vectorint(n,INT_MAX)); for(int j 0; j n; j) { dp[0][j] 0; } for(int i 1; i m; i) { for(int j 1; j n - 1; j) { dp[i][j] min(dp[i-1][j], min(dp[i - 1][j-1],dp[i-1][j1])) ma[i-1][j-1]; } } int tmp INT_MAX; for(int j 1; j n -1; j) { tmp min(tmp,dp[m-1][j]); } return tmp; } };9.地下城游戏1.状态表示 dp[i][j]位置处到达终点所需要的最低健康点数此处作为起点 如果某处作为终点那么因为该处接受所需的健康点数与从该处出去之后所增加或减少的健康点数有关因此不能依靠前一步确定这一步 2.状态转移方程 dp[i][j] dg[i][j] dp[i][j1] 或 dp[i][j] dg[i][j] dp[i1][j] 某一个位置到结束时后所需要的最低健康点数此处的所得的健康点数可能为负数 要大于等于下一个位置到结束后需要的最低健康点数。取最小的值 终点实际上是右下角格子再向右或者向下一格因为这个格子也有增加以及减少健康的判定 如果某个地方提供的健康值很大那么会出现即使通过这个地方之前勇士的健康值为负数他依旧可以顺利通过但显然是不符合题意的所以dp[i][j] 1,每次要与1取大 3.初始化 先把全部位置初始化为INT_MAX选择最小值时就不会影响到选值 把右下角格子的右边以及下面的位置初始化为1脱离右下角格字结束时最小的健康值为1要保证勇士存活 4.填表顺序 从下到上从右到左 5.返回值dp[0][0]class Solution { public: int calculateMinimumHP(vectorvectorint dg) { int m dg.size(); int n dg[0].size(); vectorvectorint dp(m1,vectorint(n1, INT_MAX)); dp[m][n-1] 1; dp[m-1][n] 1; for(int i m - 1; i 0; i--) { for(int j n - 1; j 0;j--) { dp[i][j] min(dp[i][j1], dp[i1][j]) - dg[i][j]; dp[i][j] max(1,dp[i][j]); } } return dp[0][0]; } };10.class Solution { public: int massage(vectorint nums) { int size nums.size(); if(size 0)return 0; vectorint dpfx(size); vectorint dpgx(size); dpfx[0] nums[0]; for(int i 1; i size; i) { dpfx[i] dpgx[i-1] nums[i]; dpgx[i] max(dpfx[i-1],dpgx[i-1]); } return max(dpfx[size-1],dpgx[size-1]); } };三、简单多状态dp10.按摩师1.状态表示 有两种不同的状态需要分开讨论 dpfx[i]在i位置时接i位置的预约时候时间的最大值 dpgx[i]在i位置时不接i位置的预约时候时间的最大值 2.状态转移方程 dpfx[i] dpgx[i-1] n[i] dpgx[i] max(dpfx[i-1],dpgx[i-1])//这里只需要考虑前一步的就行了 3.初始化 dpfx[0]n[0] dpgx[0]0 4.填表顺序 从左到右 5.返回值max(dpfx[size-1],dpgx[size-1])class Solution { public: int massage(vectorint nums) { int size nums.size(); if(size 0)return 0; vectorint dpfx(size); vectorint dpgx(size); dpfx[0] nums[0]; for(int i 1; i size; i) { dpfx[i] dpgx[i-1] nums[i]; dpgx[i] max(dpfx[i-1],dpgx[i-1]); } return max(dpfx[size-1],dpgx[size-1]); } };11.打家劫舍1.状态表示 有两种不同的状态需要分开讨论 f[i]在i位置时打劫此家所得钱财最大值 g[i]在i位置时不打劫此家所得钱财最大值 2.状态转移方程 f[i] g[i-1] nums[i] //虽然打劫此家后面一家也不能打劫但是只需要考虑前面的一步后一家不抢的 //情况会在i1的时候讨论 g[i] max(f[i-1],g[i-1]) 3.初始化 f[0] nums[0] g[0] 0 4.填表顺序 从左到右 5.返回值max(f[size-1],g[size-1])class Solution { public: int rob(vectorint nums) { int size nums.size(); vectorintf(size); vectorintg(size); f[0] nums[0]; for(int i 1; i size; i ) { f[i] g[i-1] nums[i]; g[i] max(f[i-1],g[i-1]); } return max(f[size-1],g[size-1]); } };12.打家劫舍2分解成两个打家劫舍问题第一个是第一家不偷把后面看成一个整体第二个是第一家偷并且最后一家不偷把剩下的看成一个整体class Solution { public: int rob(vectorint nums) { int size nums.size(); return max(nums[0]rob1(nums,2,size-2), rob1(nums,1,size-1)); } int rob1(vectorint nums, int left,int right) { if(left right)return 0; int size nums.size(); vectorintf(size); vectorintg(size); f[left] nums[left]; for(int i left1; i right; i ) { f[i] g[i-1] nums[i]; g[i] max(f[i-1],g[i-1]); } return max(f[right],g[right]); } };13.删除并获得点数主要思路就是把原数组里面的数值映射到新数组中把数x映射到下标为x的位置中每次找到该位置值x然后做一次打家劫舍问题。题目给定数值范围为1-10000这里取巧开了10001大小的数组。不取巧可以算出最大的值然后再开数组。class Solution { public: int deleteAndEarn(vectorint nums) { vectorintnums1(10001); for(auto ch :nums) { nums1[ch] ch; } int size nums1.size(); vectorintf(size); vectorintg(size); f[0] nums1[0]; for(int i 1; i size; i ) { f[i] g[i-1] nums1[i]; g[i] max(f[i-1],g[i-1]); } return max(f[size-1],g[size-1]); } };14.粉刷房子按照第一个房子涂的颜色需要分成三种情况讨论 每次种颜色每次更新都取在i位置涂另外两种颜色所花的钱的最小值class Solution { public: int minCost(vectorvectorint cs) { int n cs.size(); vectorvectorintdp(n,vectorint(3)); dp[0][0] cs[0][0]; dp[0][1] cs[0][1]; dp[0][2] cs[0][2]; for(int i 1; i n; i) { dp[i][0] min(dp[i-1][1],dp[i-1][2]) cs[i][0]; dp[i][1] min(dp[i-1][0],dp[i-1][2]) cs[i][1]; dp[i][2] min(dp[i-1][0],dp[i-1][1]) cs[i][2]; } return min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]); } };15.买卖股票的最佳时机含冷冻期dp[0/1/2][i]表示当前处于股票买入/可交易/冷冻期状态时可获得的最大利润 这里比较重要的是状态机的概念画出三个 状态分别分析另外两个状态到自己以及自己到自己的状态就不缺不漏了。class Solution { public: int maxProfit(vectorint pr) { int size pr.size(); vectorvectorintdp(3,vectorint(size)); dp[0][0] -pr[0];//要处于已经买入股票的状态需要先买股票 //因为先前没有交易要进入可交易状态就只能是什么都不干利润0 //冷冻期可以理解为在这天的前一天买入又卖出同一股票利润0 for(int i 1; i size; i) { dp[0][i] max(dp[0][i-1],dp[1][i-1]-pr[i]);//每次分析其它状态到达此状态的最大利润 dp[1][i] max(dp[1][i-1],dp[2][i-1]); dp[2][i] dp[0][i-1]pr[i]; } return max(dp[1][size-1],dp[2][size-1]);//这里是一点优化最后手持股票肯定不是利润最大 //的 } };16.买卖股票的最佳时机含手续费. - 力扣LeetCodeclass Solution { public: int maxProfit(vectorint pr, int fee) { int size pr.size(); vectorintf(size); f[0]-pr[0]; vectorintg(size); for(int i 1; i size; i) { f[i] max(f[i-1],g[i-1]-pr[i]); g[i] max(g[i-1],f[i-1]-feepr[i]); } return g[size-1]; } };原理同上但是只有两个状态了只需要在卖出时候减去手续费就可以了17.买卖股票的最佳时机三. - 力扣LeetCodeclass Solution { public: int maxProfit(vectorint pr) { int size pr.size(); vectorvectorintf(size,vectorint(3)); vectorvectorintg(size,vectorint(3)); for(int j 0;j 3; j)f[0][j] -pr[0]; for(int i 1; i size; i) { for(int j 0;j 3;j) { f[i][j] max(f[i-1][j],g[i-1][j]-pr[i]); g[i][j] g[i-1][j]; if(j 0) { g[i][j] max(g[i][j],f[i-1][j-1]pr[i]); } } } int maxmoney 0; for(int j 0; j 3;j) { maxmoney max(maxmoney,g[size-1][j]); } return maxmoney; } };是第十八题的特例详见十八题18.买卖股票的最佳时机四class Solution { public: int maxProfit(int k, vectorint pr) { int size pr.size(); vectorvectorintf(size,vectorint(k1)); vectorvectorintg(size,vectorint(k1)); for(int j 0;j k1; j)f[0][j] -pr[0]; for(int i 1; i size; i) { for(int j 0;j k1;j) { f[i][j] max(f[i-1][j],g[i-1][j]-pr[i]); g[i][j] g[i-1][j]; if(j 0) { g[i][j] max(g[i][j],f[i-1][j-1]pr[i]); } } } int maxmoney 0; for(int j 0; j k1;j) { maxmoney max(maxmoney,g[size-1][j]); } return maxmoney; } };因为g[][]中下标j可能会有越界的风险所以可以先判断再比较。初始化时当在第一天时交易次数无论是几次处于买入状态的利润都是-pr[0]每一整次交易都相当于买了又卖同一支股票而处于卖出的则都是0.小知识最大最小整数的一半某些情况下 考虑到INT_MIN经过减 INT_MAX在经过加后会出现数值巨大的变化因此我们可以使用0x3f3f3f3f,即最大整型的一半四、子数组系列19. 最大子数组和需要注意的一点是在dp[i]处需要比较nums[i-1]与dp[i-1]nums[i-1]的大小因为有两种个大类* nums[i-1] ** 这里可以看成以nums[i-2]为结尾的的子数组 nums[i-1] 即为dp[i-1]nums[i-1] *** **** ***** ******class Solution { public: int maxSubArray(vectorint nums) { int size nums.size(); vectorintdp(size1); int ret INT_MIN; for(int i 1; i size; i) { dp[i] max(dp[i-1]nums[i-1], nums[i-1]); ret max(dp[i],ret); } return ret; } };20环形子数组的最大和因为是环形所以会出现两部分隔开的情况那么这个时候我们可以把问题转换在19题的基础上转变为求最小子数组和然后将总大小减去最小子数组剩下的就是最大的了。但是还需要额外考虑的一点是如果数组全为负数出现了最小子数组和即为该数组和的大小那么第二种方法就不能用直接考虑第一种情况即可class Solution { public: int maxSubarraySumCircular(vectorint nums) { int size nums.size(); vectorintdp(size1); int s 0; int ret INT_MIN; for(int i 1; i size; i) { dp[i] max(dp[i-1]nums[i-1], nums[i-1]); ret max(dp[i],ret); s nums[i-1]; } int ret2 INT_MAX; for(int i 1; i size; i) { dp[i] min(dp[i-1]nums[i-1],nums[i-1]); ret2 min(dp[i],ret2); } if(ret2 s)return ret; else return(max(ret,s-ret2)); } };21.乘积最大子数组(最后一种情况针对用例解决解法尚有问题)这里主要思路还是和19一样分成* 两种********************但是如果nums[i]为负数那么乘以一个大数反而变小了因此需要分成nums[i]大于等于和小于0两种情况两个dp表一个存最大值一个存最小值class Solution { public: int maxProduct(vectorint nums) { int size nums.size(); vectorintf(size1); vectorintg(size1); f[0] g[0] 1; int retmax INT_MIN; for(int i 1; i size; i) { int x nums[i-1]; int y nums[i-1]*f[i-1]; int z nums[i-1]*g[i-1]; f[i] max(max(x,y),z); g[i] min(min(x,y),z); retmax max(f[i],retmax); if(retmax 1000000000)return retmax;//这里是针对最后一个用例特殊举出来的 } return retmax; } };22.乘积为正整数的最长子数组长度* 两种********************首先仍然分成两组对于fx[i]即以i元素为结尾的所有子数组中乘积为正数的最长长度长度为1 nums[i] 0 --1nums[i] 0 --0nums[i] 0 ---0长度大于1nums[i] 0 --f[i-1]1nums[i] 0 --0nums[i] 0 ---g[i-1] 0 --- 0g[i-1] ! 0 ----g[i-1] 1易得长度大于1时nums[i]始终大于等于当长度为1时的nums[i],因此可以省略比较对于gx[i]即以i元素为结尾的所有子数组中乘积为负数的最长长度),结果同上nums[i] 0 --g[i-1]1nums[i] 0 --0nums[i] 0 ---f[i-1] 0 --- 0f[i-1] ! 0 ----f[i-1] 1所以把nums[i]的值分成三种情况讨论就可以了每次得到f[i]时记录最大值class Solution { public: int getMaxLen(vectorint nums) { int size nums.size(); vectorintfx(size1); vectorintgx(size1); int maxs INT_MIN; for(int i 1; i size; i) { if(nums[i-1] 0) { fx[i] 1fx[i-1]; if(gx[i-1] ! 0) gx[i] 1gx[i-1];//如果前面凑不出为负数的情况并且这里是正 //数负数的值就加不了 } else if(nums[i-1] 0) { fx[i] 0; gx[i] 0; } else { if(gx[i-1]! 0)fx[i] 1 gx[i-1];//如果前面凑不出来结果为负数的情况如果这 //里还为负数那么就出不了为正数的结果 gx[i] 1 fx[i-1]; } maxs max(fx[i],maxs); } return maxs; } };附加 跳跃游戏2. - 力扣LeetCodeclass Solution { public: int jump(vectorint nums) { int size nums.size(); vectorintdp(size,0x3f3f3f3f);//状态转移方程还是题意与经验为主 dp[0] 0; for(int i 0; i size; i) { int x 0; while(x nums[i]) { if(i x size) { dp[ix] min(dp[i]1,dp[ix]); } x; } } return dp[size-1]; } };dp[i]表示跳到这个位置所需要的最小次数,并且是作为一个起始位置。dp[ix] min(dp[i]1,dp[ix]);需要在x的取值需要在[0,nums[i]]中遍历或者[1dp[ix]]也可以这里是从它本身开始向后当x等于0时这个dp[i] dp[i]不影响结果初始化的时候使用一个较大的数字防止取min的时候干扰取值。dp[0]跳跃的次数为0.23.等差数列划分413. 等差数列划分 - 力扣LeetCode这里如果新的那个位置可以与前两个数构成等差数列那么最后不仅自身是一个等差数列也可以继承前面的等差数列所以状态转移方程为dp[i] dp[i-1] 1,如果不能构成等差数列那么就什么都没有了dp[i]就为0.class Solution { public: int numberOfArithmeticSlices(vectorint nums) { int n nums.size(); vectorint dp(n , 0); int ret 0; for(int i 2; i n; i) { if(nums[i] - nums[i-1] nums[i-1] - nums[i-2]) { dp[i] dp[i-1] 1; } else { dp[i] 0; } ret dp[i]; } return ret; } };24.最长湍流子数组978. 最长湍流子数组 - 力扣LeetCode和等差数列的划分其实比较类似我们的判断条件是临近的三个数之间相互之间的大小关系相反即( ( arr[i] - arr [i - 1] 0 arr[i-1] - arr[i-2] 0) ||(arr[i] - arr [i - 1] 0 arr[i-1] - arr[i-2] 0))而一旦成立我们这个新的湍流数组的长度就变成了3我们需要和dp[i-1] 1取max。因为已经成为湍流数组的数组内每两个位置的大小关系都相反因此我们只需要比较最末尾三个数即可不成立的情况下如果末两个数大小相等那么dp[i]为1否则为2.初始化dp表的时候我们因为要用到dp[i-2]因此把最开始的两个位置给初始化了。class Solution { public: int maxTurbulenceSize(vectorint arr) { int n arr.size(); vectorint dp(n, 1); int ret 1; if(n 1 arr[0] ! arr[1]) { dp[1] 2; ret 2; } for(int i 2; i n; i) { if( ( arr[i] - arr [i - 1] 0 arr[i-1] - arr[i-2] 0) || (arr[i] - arr [i - 1] 0 arr[i-1] - arr[i-2] 0)) { dp[i] max(dp[i-1]1, 3); } else { if(arr[i] arr[i-1])dp[i] 1; else{ dp[i] 2; } } ret max(ret, dp[i]); } return ret; } };25.单词拆分139. 单词拆分 - 力扣LeetCode由于j会存在越界问题所以我们可以加一个节点放一个空格在字符串最前边即s s;同时dp[0]也初始化为1.class Solution { public: unordered_setstring hash; bool wordBreak(string s, vectorstring wordDict) { for(auto ch: wordDict) hash.insert(ch); int n s.size(); vectorint dp(n1, 0); dp[0] 1; s s; for(int i 1; i n; i) { for(int j i; j 1; j--) { if(dp[j-1] hash.count(s.substr(j, i - j 1))) { dp[i] 1; break; } } } return dp[n]; } };26.环绕字符串中唯一的子字符串467. 环绕字符串中唯一的子字符串 - 力扣LeetCode由于每个位置它本身就是一个字串所以我们在初始化的时候可以把dp表内的值初始化为1.更新dp表的时候直接让dp[i] dp[i-1]即可另一个需要注意的点是我们需要去重。例如上图1中有两个c我们只需要统计一个c。例如上图2中如果有一个字符串为a,b,c,y,z,a,b,c, 题目中要我们统计 不同非空子串由于a,b,c中的字串一定是被包含在y,z,a,b,c,中的因此只需要统计yzabc这个串里面不同字串的数目。也就是说相同字母结尾的字串我们只需要统计更长的那个的不同字串数目也就是取更大的dp值class Solution { public: int findSubstringInWraproundString(string s) { int n s.size(); int ret 0; vectorint dp(n1, 1); vectorint count(200, 0); s s; for(int i 2 ; i n; i) { if(s[i] s[i-1] 1 || (s[i] a s[i-1] z)) { dp[i] dp[i-1]; } } for(int i 1; i n; i) { count[s[i]] max(count[s[i]], dp[i]); } for(auto ch: count) { ret ch; } return ret; } };