不清楚动态规划是什么的同学先看看我的上一篇
双指针+动态规划(上)力扣解析_lihua777的博客-CSDN博客双指针+动态规划(上)力扣解析https://blog.csdn.net/lihua777/article/details/122650138?spm=1001.2014.3001.5501话不多说,我们直接上力扣题目解析:
目录
1:打家劫舍
思路解析:
2:打家劫舍||
思路解析:
3:删除点数
思路解析:
4:跳跃游戏(动态规划+贪心)
思路解析:
5:跳跃游戏||
思路解析:
第一种方法:暴力+从尾向头法:
第二种方法:动态规划+贪心
6:最大子组数和
思路解析:
7:乘积最大子数组
思路解析:
8:最佳观光组合
思路解析:
9:买卖股票的最佳时机
思路解析:
10:买卖股票的最佳时机||
思路解析:
结语:
1:打家劫舍 思路解析:
(1)当只有一个房屋时,最大金额就是这个了,即:maxprofit=nums[0]
(2)当有两个房屋时,选择两个房屋中金额最高的,即:maxprofit=max(nums[0],nums[1])
(3)我们重点要考虑的问题是,当房屋的数量>2个时的情况:
我们就要找到递推关系:既然不能间隔,那么情况应该分为两种:
1:我既然拿到了nums[i-1],我就不能拿nums[i]
2:我拿了nums[i-2],我还能拿nums[i]
是不是有点熟悉了^ ^
没错青蛙跳台阶问题!
只不过我们还要动态规划在这两者中选择最大值:
代码实现:核心的递推公式!
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
完整代码:
class Solution { public: int rob(vector& nums){ if (nums.empty()) { return 0; } int size = nums.size(); if (size == 1) { return nums[0]; } vector dp = vector (size, 0); dp[0] = nums[0]; dp[1] = max(nums[0], nums[1]); for (int i = 2; i < size; i++) { dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[size - 1]; } };
问:为什么返回的是dp[size-1]?
答:因为数组的最后一位的索引是size-1
2:打家劫舍|| 思路解析:
这道题的的难点就在于,它是一个环状的,因此在首尾处要特别小心,不能既选首又选尾!
这就是与上题的区别,那么我们就可以对这个区别进行分类讨论,让它成为我们的上一题的想法!
1:首先创建两个容器
f(n+1)和g(n+1) ->为什么要定义n+1的大小? ->为了好看(下标对应)
f(1)=nums[0]; -> 表示从原数组的首位置开始
g(2) =nums[1]: ->表示从原数组索引为1的位置开始
2:f(n+1)的递推
for (int i = 2; i <= n - 1; i++)
f[i] = max(f[i - 1], f[i - 2] + nums[i-1]);//区间[1,n-1]的最大值
由此可知f(2)=max(nums[0],nums[1]) ->f(2)才是真正的开始!
f(3)=max(f[2],nums[0]+nums[2]) //接着递推
3:g(n+1)的递推
for (int i = 3; i <= n; i++)
g[i] = max(g[i - 1], g[i - 2] + nums[i-1]);//区间[2,n]的最大值
由此可知g(3)=max(nums[1],nums[2]) ->g(3)才是真正的开始!
g(4)=max(g[3],nums[1]+nums[3]) //接着递推
4:两者中求最大
return max(f[n-1], g[n]);//两者中取最大返回
注意:因为两个数组的边界不同,所以返回的索引不同!
完整代码:
class Solution { public: int rob(vector& nums) { int n = nums.size(); if (n == 1)//只有一间房间时 { return nums[0];//返回nums[0] } vector f(n + 1), g(n + 1);//因为我们要用到n这个索引 f[1] = nums[0]; g[2] = nums[1]; for (int i = 2; i <= n - 1; i++) { f[i] = max(f[i - 1], f[i - 2] + nums[i-1]);//区间[1,n-1]的最大值 } for (int i = 3; i <= n; i++) { g[i] = max(g[i - 1], g[i - 2] + nums[i-1]);//区间[2,n]的最大值 } return max(f[n-1], g[n]);//两者中取最大返回 } };
问:为什么是f[i-2]或是g[i-2] +nums[i-1]?
答:因为这里实际上我们是为了对应f,g的索引,所以nums的索引要做出牺牲,就是稍微改变一下,因为创建的f,g数组长度是n+1,所以它对应的 nums[i]-> nums[i-1]
3:删除点数 思路解析:
我们发现如果删除一个数,它的+1,-1的数不存在于这个数组,那么这种情况就是最赚的,即没有对我的点数造成亏损,那么我们怎么知道数组中的元素它的+1 -1 的数是否在这个数组呢?
可以遍历,但是会有很多没有必要的 *** 作,使得这个程序的性能降低
一般有频数问题的时候,会联想到哈希表
不过我们这里的哈希不是用来存储数字出现的频数,而是相当于创建一个以原数组(nums)最大值+1长度的数组sum,并将它排序,数字相同就加起来…………这个用人话说确实有点绕
直接代码实现:
int deleteAndEarn(int* nums, int numsSize) { int maxVal = 0; for (int i = 0; i < numsSize; i++) { maxVal = fmax(maxVal, nums[i]); } //maxVal是nums数组中的最大值 int sum[maxVal + 1]; memset(sum, 0, sizeof(sum));//memset函数,作用是将数组初始化为0 for (int i = 0; i < numsSize; i++) { sum[nums[i]] += nums[i];//哈希,懂得都懂,谅我表达能力有限 } return rob(sum, maxVal + 1);//传这个数组和长度//下面将 }
之后就是打家劫舍的问题了:即如果你选择了一个数,那么你就不能选择与它相邻的两个数
代码实现:
int rob(int* nums, int numsSize) { int first = nums[0], second = fmax(nums[0], nums[1]); for (int i = 2; i < numsSize; i++) { int temp = second; second = fmax(first + nums[i], second); first = temp; } return second; }
解释:这个是C语言是实现的递推,因为在VS2022编译器上无法创建以变量初始化数组,实质是翻滚数组,下面是C++的DP版本
C++版本:这里的哈希就是真正记录的是频数了,我已经把它修改为很好理解的版本了^ ^
#include#include using namespace std; class Solution { public: int deleteAndEarn(vector & nums) { if (nums.empty()) return 0; int maxVal = nums[0]; for (int i = 0; i < nums.size(); i++) { maxVal = max(maxVal, nums[i]); } vector dp(maxVal + 1), sum(maxVal + 1); for (int i = 0; i < nums.size(); i++) { sum[nums[i]]++; //sum数组用来记录nums中出现数字的个数 } dp[1] = sum[1]; for (int j = 2; j <= maxVal; j++) { dp[j] = max(dp[j - 1], dp[j - 2] + j * sum[j]);//因为是频数所以+j*sum[j] } return dp[maxVal]; } };
4:跳跃游戏(动态规划+贪心) 思路解析:
定义一个右边界步长,如果右边界的步长大于nums.size()-1即可到达最后一个元素,反之不行
右边界步长=i(当前位置下标)+nums[i]该下标所对应的元素数值
当右步长>=i时,说明可以继续走,接着,我们用动态规划来记录,最大的右边界步长
即:有边界步长=max(右边界步长,i+nums[i])
代码实现:
class Solution { public: bool canJump(vector5:跳跃游戏|| 思路解析:& nums) { int n = nums.size(); int rightmost = 0; for (int i = 0; i < n; i++) { if (i <= rightmost) { rightmost = max(rightmost, i + nums[i]); if (rightmost >= n - 1) { return true; } } } return false; } };
这题与上题不同的地方在于,本题求的是最小步长,判断条件依然是
如果右边界>=nums.size()-1 即可到达最后一个位置
此外我们还需要一个step,来记录我们所走的步数
既然是最小步长,那么我们就要尽可能保证我们选择的都是点数大的位置
第一种方法:暴力+从尾向头法:#include第二种方法:动态规划+贪心using namespace std; int jump(vector & nums) { int position = nums.size() - 1; int steps = 0; while (position > 0) { for (int i = 0; i < position; i++)//从头开始遍历,寻找第一个满足条件的位置 { if (i + nums[i] >= position)//如果满足 { position = i;//将尾端移动到i这个位置 steps++;步数+1 break;//跳出for循环,重新寻找第一个满足条件的位置,直至该位置==0 } } } return steps; }
int jump(vector& nums) { int max_far = 0;// 目前能跳到的最远位置 int step = 0; // 跳跃次数 int end = 0; // 上次跳跃可达范围右边界(下次的最右起跳点) for (int i = 0; i < nums.size() - 1; i++) { max_far = max(max_far, i + nums[i]); // 到达上次跳跃能到达的右边界了 if (i == end) { end = max_far; // 目前能跳到的最远位置变成了下次起跳位置的有边界 step++; // 进入下一次跳跃 } } return step; }
解释:如果你想要+ if(max_far>nums.size()-1) break 可以是可以,我也是这么想的,但是并没有提升运行速度 = =
6:最大子组数和 思路解析:
相信经过了这么多的训练,这道题相信对大伙已经非常简单了,我们把初始索放在1位置,并判断如果前一个数>0,我们即让它上车,它既然>0,那么拉它上车肯定是对我们有所增加的,上车的 *** 作是:nums[i]=nums[i]+nums[i-1],接着nums[i]的值会发生变化,然后i++ -> i=2;
判断nums[i-1]是否>0,如果大于0,我们就拉它上车,否则不管它…………
最后我们得到的数组已经发生彻头彻尾的改变,比如:
经过变形:
它的实质是:
把如果上一个是正数我就把它加给我自己,如果我自己加了它之后是正数,我再把自己加个下一个,以此达到最大子数和的效果;如果我加了上一个正数后,我仍然是负数,那么再把我加给下一个,会让大家都变小。所以此时要舍弃我
分析好后,代码其实很简单:得到一个新数组,再求出这个数组的最大值即是:最大子数列和
int Max(int* nums, int numsSize) { int max = nums[0]; for (int i = 0; i < numsSize; i++) { if (max < nums[i]) { max = nums[i]; } } return max; } int maxSubArray(int* nums, int numsSize) { if(numsSize==1) { return nums[0]; } else { for (int i = 1; i < numsSize; i++) { if (nums[i - 1] > 0) { nums[i] = nums[i] + nums[i - 1]; } } return Max(nums,numsSize); } }
7:乘积最大子数组 思路解析:
本题看似容易,实质上要考虑多个方面,但是不用担心,我呈现的都是我觉得最简单最容易理解的写法。
(1):当数组元素都是正数时,非常简单
(2):当数组元素有正有负时,这是我们着重考虑的情况:
假设我们已经存有一个最大值,当遍历到一个负数时,它变为了最小值
又假设我们已经存有一个最小值,当遍历到一个负数,它变为了最大值
最小值和最大值在不断的变化,而使它们相反的原因是正负,所以:
当遍历到一个数是正数时:最大值=max(该值,max*该值) 最小值=min(该值,min*该值)
当遍历到一个数是负数时:最大值=max(最小值*该值,该值) 最小值=min(最大值*该值,该值)
(3):当遍历到0时,我们这时应重新让最大值=最小值=0
分析好了,冻手起来非常简单
class Solution { public: int maxProduct(vector& nums) { int n = nums.size(); int dpmin = nums[0]; int dpmax = nums[0]; int res = dpmax; for (int i = 1; i < n; i++) { if (nums[i] == 0) { dpmin = dpmax = 0; } else if (nums[i] > 0) { dpmax = max(dpmax * nums[i], nums[i]); dpmin = min(dpmin * nums[i], nums[i]); } else { int tmp = dpmax;//存放最大值的变量,防止因dpmax的改变而使dpmin的值不是我们期待的 dpmax = max(dpmin * nums[i], nums[i]); dpmin = min(tmp * nums[i], nums[i]); } res = max(res, dpmax); } return res; } };
问:为什么在else:还要int tmp=dpmax?
答:防止因dpmax的改变而使dpmin不是我们期待的改法
8:最佳观光组合 思路解析:
题目要求的是:values[i]+values[j]+i-j的最大值
两个循环的暴力解法会导致时间超出限制
那么我们就动态规划 以空间的消耗来换取运行时间的减少!
既然不能用两个for循环,那么我们可以开两个动态规划,只需一遍遍历,就可以推动寻找最大值
那么我们需要找到变量和常量
暂且把:values[i]+i 看作变量 -> mx
把:values[j]-j看作常量
ans=mx+values[j]-j
在for循环里,一个存的是ans即答案的动态,一个存的是mx的动态
代码实现:
class Solution { public: int maxScoreSightseeingPair(vector& values) { int ans = 0, mx = values[0] + 0;//只是为了让形式看起来一致 for (int j = 1; j < values.size(); ++j) { ans = max(ans, mx + values[j] - j); // 边遍历边维护 mx = max(mx, values[j] + j); } return ans; } };
9:买卖股票的最佳时机 思路解析:
定义一个min=prices[0],和maxprofit=0,遍历数组,
对maxprofit进行动态规划
如果price>min : maxprofit=max(maxprofit,prices[i]-min)
否则 : min=prices[i](如果价格比最小值还低,那么就让价格低的成为最小值)
代码实现:
int maxProfit(int* prices, int pricesSize) { int maxPro = 0; int min = prices[0]; for (int i = 1; i < pricesSize; i++) { if (prices[i] > min) { maxPro = fmax(maxPro, prices[i] - min); } else if (prices[i] < min) { min = prices[i]; } } return maxPro; }
10:买卖股票的最佳时机|| 思路解析:
这实际上是最简单的一题= =,还搞啥动态规划啊,只要下一个比上一个高,我直接卖掉,直接得利润,如果不是,那我就等直到下一个比上一个高
代码实现:
int maxProfit(int* prices, int pricesSize) { if (pricesSize == 0) { return 0; } int profit = 0; //当价格高于前一天时,将差价计入利润中,直至遍历结束,即可获得总利润 for (int i = 1; i < pricesSize; i++) { if (prices[i] > prices[i - 1]) { profit = profit + (prices[i] - prices[i - 1]); } } return profit; }
结语:
算法虽难,但有规律模板套路可循= =
我一定会努力更新的!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)