网站后台seo设置,wordpress wmv,阜阳h5网站建设,wordpress装在xampp动态规划#xff1a;路径和子数组问题 路径问题1.不同路径#xff08;中等#xff09;2.不同路径II#xff08;中等#xff09;3.下降路径最⼩和#xff08;中等#xff09;4.地下城游戏#xff08;困难#xff09; 子数组问题1.最大子数组和#xff08;中等#xf… 动态规划路径和子数组问题 路径问题1.不同路径中等2.不同路径II中等3.下降路径最⼩和中等4.地下城游戏困难 子数组问题1.最大子数组和中等2.环形子数组的最大和中等3.乘积最大子数组中等4.乘积为正数的最长子数组中等5.等差数列划分中等6.最长湍流子数组中等7.单词拆分中等8.环绕字符串中唯⼀的子字符串中等 路径问题
1.不同路径中等
链接不同路径 题目描述 做题步骤 状态表示 尝试定义状态表示为到达[m, n]位置的路径数。 状态转移方程 通过上述分析可知状态转移方程为dp[i][j] dp[i - 1][j] dp[i][j - 1]。 初始化 填表顺序 保证填当前状态时所需状态已经计算过从起点出发填表顺序为从上往下每一行从左往右。 返回值 根据状态表示返回的应该是dp[m][n]即到达终点的路径数。
代码实现
class Solution {
public:int uniquePaths(int m, int n) {//dp[i][j]表示到达该位置的路径vectorvectorint dp(m1, vectorint(n1,0));dp[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];//时间复杂度O(N)//空间复杂度O(N^M)}
};//滚动数组优化
// class Solution {
// public:
// int uniquePaths(int m, int n)
// {
// vectorint dp(n 1);
// dp[1] 1;// for(int i 1; i m; i)
// {
// for(int j 1; j n;j)
// {
// dp[j] dp[j-1];
// }
// }
// return dp[n];
// }
// };2.不同路径II中等
链接不同路径II 题目描述 做题步骤 状态表示 这个题和第一题唯一不同就是加入了障碍物1我们只需要进行判断如果该位置是障碍物就填0否则依据转移方程填表。 状态转移方程 通过上述分析可知状态转移方程为dp[i][j] dp[i - 1][j] dp[i][j - 1]。 初始化 和第一题一样多开一圈dp[0][1]或dp[1][0]初始为1。 填表顺序 和第一题一样填表顺序为从上往下每一行从左往右。 返回值 根据状态表示返回的应该是dp[m][n]即到达终点的路径数。
代码实现
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();//dp[i][j]到达该位置的路径数vectorvectorint dp(m 1,vectorint(n 1));dp[0][1] 1; //dp[1][0] 1;for(int i 1; i m 1; i){for(int j 1; j n 1; j){//多开了一圈注意下标映射if(obstacleGrid[i - 1][j - 1] 0){dp[i][j] dp[i-1][j] dp[i][j-1];}//vector默认初始0障碍物对应位置无需处理}}return dp[m][n];//时间复杂度O(N)//空间复杂度O(N^2)}
};3.下降路径最⼩和中等
链接下降路径最⼩和 题目描述 做题步骤 状态表示 状态转移方程 由前面的分析可知状态转移方程为 dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j 1]}) matrix[i - 1][j - 1](本身的值 初始化 先全部初始化为极大值然后第一行初始化为0。 填表顺序 从上往下每一行从左往右。 返回值 依据状态表示和题目要求返回最后一行的最小值即可。
代码实现
class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {//dp[i][j]表示到这个位置最小路径和int n matrix.size();vectorvectorint dp(n 1, vectorint(n 2, INT_MAX));//初始化第一行for(int j 0; j n 2; j){dp[0][j] 0;}for(int i 1; i n 1; i){for(int j 1; j n 1; j){dp[i][j] min({dp[i-1][j-1], dp[i-1][j], dp[i-1][j1]}) matrix[i - 1][j - 1]; }}//再遍历一次找最小int ret dp[n][0];for(auto e : dp[n]){ret min(ret, e); }return ret;//时间复杂度O(N)//空间复杂度O(N^2)}
};4.地下城游戏困难
链接地下城游戏
题目描述 做题步骤
状态表示 状态转移方程 由前面的分析可知状态转移方程为 dp[i][j] min(dp[i][j 1], dp[i 1][j]) - dungeon[i][j](自身出去的消耗 初始化 先将所有值初始化为极大值dp[m][n - 1] dp[m - 1][n] 1。 填表顺序 从下往上每一行从右向左。 返回值 由状态表示可知返回值为dp[0][0]即[0,0]位置到终点需要的最小生命
代码实现
// 看点位的状态表示
//从左上到右下点位表示到这里需要的最小健康点数点位并不是只受到左边和上面的影响也要受后面点位的影响后面点位可能使自己死亡这种状态表示肯定不能//从右下到左上点位表示从这里开始到终点所需要的最小健康点数。class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {//dp[i][j]表示以这个位置为起点到终点所需要的最小健康点数int m dungeon.size();int n dungeon[0].size();vectorvectorint dp(m 1, vectorint(n 1, INT_MAX));//初始化dp[m][n - 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][j 1], dp[i 1][j]) - dungeon[i][j];//如果dp[i][j]为负数说明这个位置是奶//直接奶满了从这里到终点所要的点数1就足够小于1就死了dp[i][j] max(dp[i][j], 1);}}return dp[0][0];//时间复杂度O(N)//空间复杂度O(N^2)}
};子数组问题
1.最大子数组和中等
链接最大子数组和
题目描述 做题步骤 状态表示 这个题目我们可以定义状态表示为以i位置为结尾的子数组的最大和。 因为子数组必须是连续的所以i位置有两种选择 (1)接在以i - 1位置为结尾的子数组后面即dp[i] dp[i - 1] 自身点数 (2)不接在别人后面(可能dp[i - 1]是负值)就自己一个即dp[i] 自身点数 从两种选择中选择最大的一种即dp[i] max(dp[i -1] 自身点数, 自身点数) 状态转移方程 由前面的分析可知状态转移方程为 dp[i] max(dp[i -1] 自身点数, 自身点数) 初始化 无需初始化。 填表顺序 从左往右。 返回值 无法直接确定最大子数组的结尾位置可以定义变量ret一边dp一边更新最大值。
代码实现
class Solution {
public:int maxSubArray(vectorint nums) {//在原数组上面dp就行//dp[i]以i位置为结尾的最大子数组和int ret nums[0];for(int i 1; i nums.size(); i){nums[i] max(nums[i - 1] nums[i], nums[i]);//遍历的过程顺便找最大ret max(ret, nums[i]); } return ret;//时间复杂度O(N)//空间复杂度O(1)}
};2.环形子数组的最大和中等
链接环形子数组的最大和 题目描述 做题步骤 状态表示 这个题目和前一题类似我们依然可以定义状态表示为以i位置为结尾的最大子数组和。 对于环形问题最常见的做法就是分情况讨论分解问题 (1)最大子数组不成环比如[-1,2,3,-1]这个情况做法和前一道题一样。 (2)最大子数组成环比如[2,1,-3,-2,1]最大子数组成环情况数组中剩余的连续部分一定是最小子数组。 子数组是连续的环形可以理解为左右扩张所有有利于自己的连续部分一定会被吞并剩下的一定是最小子数组和。 但数组的总和是不变的我们只需要用总和减去最小子数组和即可得到成环情况的最大和。 状态转移方程 不成环最大子数组和用f表来记录最小子数组和用g表来记录 状态转移方程为 f[i] max(nums[i], f[i - 1] nums[i]) g[i] min(nums[i], g[i - 1] nums[i]) 初始化 为避免填表越界处理第一个位置f[0] g[0] nums[0] 填表顺序 都是从左往右。 返回值 无法直接确定最大(小)子数组的结尾所以一边dp一边记录最大(小)值。 (1)f表最大值-fmax (2)g表最小值-gmin (3)总和-sum 还有一种特殊情况就是环形数组长度为0(数组中全是负数)这个时候最大值为fmax而不是0所以返回值为sum gmin ? fmax : max(fmax, sum - gmin)。
代码实现
class Solution {
public:int maxSubarraySumCircular(vectorint nums) {int n nums.size();//一种情况是不需要环形区间就在数组中//第二种情况是需要环形数组总大小恒定//非目标区间是连续并且在数组中的所以最大 总 - 非目标区间//比如 5 -3 5第一种得到5第二种为 7(总) - (-3) 10int sum nums[0];//f[i]以i位置为结尾的不成环最大子数组和vectorint f(n);//g[i]以i位置为结尾的最小子数组和auto g f;f[0] g[0] nums[0];int fmax nums[0];int gmin nums[0];for(int i 1; i n; i){f[i] max(nums[i], f[i - 1] nums[i]);g[i] min(nums[i], g[i - 1] nums[i]);fmax max(fmax, f[i]);gmin min(gmin, g[i]);sum nums[i];}//sum和gmin相同说明里面全是负数这个时候fmax才是最大不能为0return sum gmin ? fmax : max(fmax, sum - gmin);//时间复杂度O(N)//空间复杂度O(N)}
};3.乘积最大子数组中等
链接乘积最大子数组 题目描述 做题步骤 这个题目子数组长度最小可以为1其实所有子数组默认乘了一个1。 状态表示 依据前面最大子数组和的经验我们可以定义状态为以i位置为结尾的最大乘积。 但只有这一个状态表示是不够的负数的加入对乘积影响是巨大的比如[1,2,3,-1,-2,1]前面按最大和的做法来还没问题但遇到多个负数就会出问题这里[1,2,3,-1,-2]可以得到最大乘积12如果按照最大和的做法只能得到6。 出现上面情况的原因在于负数的出现使得原来的最大乘积变成了最小乘积但如果保存最小乘积当遇到负数时最小乘积就可以变成最大乘积。 综上所述我们需要同时记录最大和最小乘积其中最大用f表记录最小用g表记录。 (1)x nums[i]当前位置的值 (2)y f[i - 1]前一个位置的最大乘积 (3)z g[i - 1]前一个位置的最小乘积 状态转移方程 一共就三种情况 (1)x不接在别人后面子数组长度为1。 (2)x * y接在前一个位置最大乘积子数组后面有可能得到最大(小)乘积。 (3)y * z接在前一个位置最小乘积子数组后面有可能得到最大(小)乘积。 由此可知状态转移方程为 f[i] max( {x, x * y, x * z} ) g[i] min( {x, x * y, x * z} ) 初始化 当前位置的f、g更新需要前一个位置第一个位置的最大(小)乘积就是值本身为了避免第一个位置越界可以在前面多开一个空间并初始化为1即f[0] g[0] 1这样不会影响第一个位置。 填表顺序 从左往右。 返回值 无法直接确定最大子数组的结尾位置一边dp一边更新最大值。
代码实现
class Solution {
public:int maxProduct(vectorint nums) {int n nums.size();//dp[i]以i为结尾的最大乘积//f[i]表示最大乘积g[i]表示最小乘积vectorint f(n 1);auto g f;f[0] g[0] 1;//ret变量记录最大乘积int ret INT_MIN;for(int i 1; i n; i){int x nums[i - 1];//现在int y f[i - 1]; //上个位置的最大乘积int z g[i - 1]; //上个位置的最小乘积//如果遇到负数的情况原本最大乘积可能会变成最小原本最小可能会变成最大f[i] max({x, x * y, x * z});g[i] min({x, x * y, x * z});ret max(ret, f[i]);}return ret;//时间复杂度O(N)//空间复杂度O(N)}
};4.乘积为正数的最长子数组中等
链接乘积为正数的最长子数组 题目描述 做题步骤 状态表示 这个题目和上一道类似要考虑负数的加入因此只有一个状态表示是不够的。 (1)f表以i位置为结尾乘积为正数的最长子数组长度。 (2)g表以i位置为结尾乘积为负数的最长子数组长度。 状态转移方程 设当前位置的值为x (1)x为负数时接在前一个位置的后面原本乘积正数的子数组会变成负数乘积负数的子数组会变成正数。 即f[i] g[i - 1] 1 和 g[i] f[i - 1] 1,但前一个位置结尾的子数组乘积可能无法出现负数前面都是正数即g[i - 1] 0这个时候f[i]应该也为0。 故状态转移方程为 f[i] g[i - 1] 0 ? 0 : g[i - 1] 1 g[i] f[i - 1] 1 (2)当x为正数时接在前一个位置的后面原本乘积正数的子数组还是正数乘积负数的子数组还是负数。 也要考虑前一个位置乘积负数不存在的情况 故状态转移方程为 f[i] f[i - 1] 1 g[i] g[i - 1] 0 ? 0 : g[i - 1] 1 初始化 当前位置的f、g更新需要前一个位置第一个位置为负数g[i]为1f[i]为0值为正数则相反。为了避免第一个位置越界可以在前面多开一个空间并初始化为0即f[0] g[0] 0这样不会影响第一个位置。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序很明显是从左往右 返回值 无法直接确定乘积为正数的最长子数组结尾位置定义变量ret一边dp一边更新最大值。
代码实现
class Solution {
public:int getMaxLen(vectorint nums) {//dp[i] 表示这个位置乘积为负数/正数时的最大长度int n nums.size();vectorint f(n 1); // 正数auto g f;//负数int ret -1;for(int i 1; i n 1; i){//这个数是正数if(nums[i - 1] 0){f[i] f[i - 1] 1;//要考虑前一个位置乘积负数不存在的情况g[i] g[i - 1] 0 ? 0 : g[i - 1] 1; }else if(nums[i - 1] 0) //负数{f[i] g[i - 1] 0 ? 0 : g[i - 1] 1;g[i] f[i - 1] 1; }//这个数为0两个状态都不存在不用处理本来就是0ret max(ret, f[i]);}return ret;//时间复杂度O(N)//空间复杂度O(N)}
};5.等差数列划分中等
链接等差数列划分
题目描述 做题步骤 状态表示 依据前面的经验我们可以定义状态表示为以i位置为结尾的等差数组个数。 状态转移方程 以[1,2,3,4]为例子进行分析 (1)像1、2这样的位置为结尾数组长度不足3是一定不能构成等差数组的即dp[i] 0。 (2)像4这样的位置先看能不能和前面两个元素构成等差数组满足nums[i] nums[i - 2] 2* nums[i - 1]如果可以的话那4也一定可以接在以3为结尾的等差数组后面即dp[i] dp[i - 1] 1。 综上所述状态转移方程为 可以和前两个数构成等差数组dp[i] dp[i - 1] 1 不能和前两个数构造等差数组dp[i] 0 初始化 无需初始化。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序很明显是从左往右 返回值 题目要求返回所有等差子数组定义变量sum一边dp一边累加。
代码实现
class Solution {
public:int numberOfArithmeticSlices(vectorint nums) {// 1 2 3 4 5//3位置1种 4位置除了拼在3位置可能的后面还可以抢2 3 来组成//4位置2种 5位置除了拼在4位置可能的后面还可以抢3 4 来组成//………………对更长的序列也是如此int n nums.size();//dp[i]以i位置为结尾的等差数组个数vectorint dp(n);int sum 0;for(int i 2; i n; i){//等差数列的性质num[i] nums[i - 2] 2 * num[i - 1]if(nums[i] nums[i - 2] 2* nums[i - 1]){dp[i] dp[i - 1] 1;}//不满足等差数组为0vector默认给0不用处理sum dp[i];}return sum;//时间复杂度O(N)//空间复杂度O(N)}
};6.最长湍流子数组中等
链接最长湍流子数组 题目描述 做题步骤 状态表示 依据前面的经验我们定义状态表示为以i位置为结尾的最长湍流子数组长度。 但只知道i-1位置的最大长度是无法推导出i位置的最大长度的因为不知道前一个最长湍流子数组结束是处于上升状态(最后的比较符号为’‘)还是下降状态(最后的比较符号为’) 因此可以对状态进行细分 1f[i]表示以i位置为结尾并处于上升状态(最后的比较符号为’)的最长湍流子数组长度 2g[i]表示以i位置为结尾并处于下降状态(最后的比较符号为’)的最长湍流子数组长度 状态转移方程 因为湍流子数组比较符号必须在每个相邻元素之间翻转所以状态转移方程与当前的比较符号相关。 1arr[i-1] arr[i]现在处于上升状态需要前置状态处于下降状态的最长湍流子数组长度即f[i] g[i - 1] 1。 2arr[i-1] arr[i]现在处于下降状态需要前置状态处于上升状态的最长湍流子数组长度即g[i] f[i - 1] 1。 3arr[i-1] arr[i]不能和前面组合只能自己重新开始即f[i] g[i] 1。 初始化 推导当前状态需要前一个状态像第一个位置不能跟在别人后面两个状态的长度都为1f[0] g[0] 1。因为arr[i-1] arr[i]时f[i] g[i] 1所以干脆一开始全都初始化为1就不用单独处理arr[i-1] arr[i]的情况。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序很明显是从左往右 返回值 无法直接确定最长湍流数组的结尾位置以及结尾是处于上升还是下降状态所以定义变量ret一边dp一边更新最大值。
代码实现
class Solution {
public:int maxTurbulenceSize(vectorint arr) {int n arr.size();//dp[i]表示以i位置为结尾并且处于上升(下降)状态的最长湍流子数组的长度 vectorint f(n, 1); //f表示处于上升()状态//初始化为1可以把的情况直接处理了auto g f; //g表示处于下降()状态int ret 1;for(int i 1; i n; i){if(arr[i-1] arr[i])f[i] g[i - 1] 1;else if(arr[i - 1] arr[i])g[i] f[i - 1] 1;ret max( {ret, f[i], g[i]} );}return ret;//时间复杂度O(N)//空间复杂度O(N)}
};7.单词拆分中等
链接单词拆分
题目描述 做题步骤 状态表示 依据前面的经验我们可以定义状态表示为以i位置为结尾的字符串能否由字典中的单词拼出。 状态转移方程 以s “leetcode”, wordDict [“leet”, “code”]为例进行分析 1先看字符’t’位置下标3位置以这个位置为结尾的字符串如果能由字典中的单词拼出一共有下面几种可能 ①lee可以由字典中的单词拼出(即dp[2] true)t也可以由字典中的单词拼出。 ②le可以由字典中的单词拼出(即dp[1] true)et也可以由字典中的单词拼出。 ③l可以由单词中的单词拼出(即dp[0] true)eet也可以由字典中的单词拼出。 ④再往前就没有了leet可以由字典中的单词拼出。 其它位置的分析也和上述一致将当前字符串分成[0, j - 1]区间和[j, i]区间从 0 ~ i 枚举 j 只要 dp[j - 1] true并且后面部分的子串 s.substr(j, i - j 1) 能够在字典中找到那么 dp[i] true 。 初始化 处理④这样的情况可以多加一个虚拟节点并初始化true(dp[0] true)可以理解为空串能在字典中找到。同时为了方便处理下标的映射关系我们可以在字符串s前面加一个占位符(s ’ ’ s)这样就不用考虑下标的映射了。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序很明显是从左往右 返回值 根据状态表示假设字符串长度为n返回的应该是dp[n] 优化 为了方便查询字符串是否在字典中可以把字典的单词存储到哈希表中。
代码实现
class Solution
{
public:bool wordBreak(string s, vectorstring wordDict) {// 将字典⾥⾯的单词存在哈希表⾥⾯unordered_setstring hash;for(auto s : wordDict) hash.insert(s);int n s.size();vectorbool dp(n 1);dp[0] true; // 保证后续填表是正确的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] true;break; //已经确定为真就可以跳出这一层循环了}}}return dp[n];//时间复杂度O(N^2)//空间复杂度O(N)}
};8.环绕字符串中唯⼀的子字符串中等
链接环绕字符串中唯⼀的子字符串
题目描述 做题步骤 状态表示 依据前面的经验我们定义状态表示为以i位置为结尾并且在base中出现的子字符串个数。 状态转移方程 这个题目中的base数组是按照abcd……zabcd这样的顺序来的要注意base成环。 以i位置为结尾并在base中出现的子字符串有下面三种可能 (1)不拼在别人后面就单独自己一个该字符串一定会在base中出现。 (2)拼在别人后面并且满足s[i] s[i - 1] 1(即满足abcd递增) (3)拼在别人后面并且满足s[i] ‘a’ s[i - 1] ‘z’(刚好成环) 综上所述状态转移方程为 ①满足(2)(3)中任意一个dp[i] dp[i - 1] 1这个1是自己,dp[i - 1]是拼在别人后面) ②不满足(2)(3)dp[i] 1 初始化 每个位置最少也有自己单独一个的情况所以全都初始化为1。 填表顺序 保证填当前状态时所需状态已经计算过填表顺序很明显是从左往右 返回值 这个题目最需要注意的就是对dp表数据的处理因为dp表中可能有大量重复的数据比如abcdcd中’d’字符出现了两次cd和d这两个字符串在dp表中是多次记录了的我们需要对dp表数据进行去重。 每个字符都对应了固定的ASCLL码因此可以可以创建⼀个大小为 26 的数组遍历dp表对于出现多次的字符只需保留以该字符为结尾的最大dp值。 去重完成后再进行累加就可以得到结果。
代码实现
class Solution {
public:int findSubstringInWraproundString(string s) {//base是abcd……连续的//s[i]表示现在位置//所以字串要存在要么s[i] s[i - 1] 1//要么(s[i - 1] z a[i]a) int n s.size();//dp[i]以i位置为结尾并且在base中出现的子字符串数vectorint dp(n, 1);for(int i 1; i n; i){if(s[i] s[i-1] 1 || (s[i-1] z s[i] a)){dp[i] dp[i - 1] 1; // 这个1是自己}}int hash[26] {0};//遍历一次统计对应字符最大的出现次数//abcdd这样的后面那个d的1是无效的要去掉for(int i 0; i n; i){int index s[i] - a;hash[index] max(hash[index], dp[i]);}//最后累加int sum 0;for(auto e : hash){sum e;}return sum;//时间复杂度O(N)//空间复杂度O(N)}
};
