不清楚动态规划是什么的同学先看看我的上一篇
双指针+动态规划（上）力扣解析_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(vector& 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;
}
};
5：跳跃游戏||
思路解析：
这题与上题不同的地方在于，本题求的是最小步长，判断条件依然是
如果右边界>=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条）