【再谈动态规划】
动态规划
- 前缀最值
- 121. 买卖股票的最佳时机
- 后缀最值
- 1299. 将每个元素替换为右侧最大元素
- 前缀最值变形
- 1014. 最佳观光组合
- 前缀+后缀 最值
- 42. 接雨水
- 结语
前缀最值
121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
链接: 买卖股票的最佳时机
要求最大利润，也就是最大值和最小值的差值，我们可以进行暴力解法，
1.枚举第i天作为买入点
2.循环遍历左开右闭区间(i,n]，寻找一个最大值作为卖出点
3.卖出点价格减去卖出点价格就是以第i天为买入点的最大利润
4.最后保留最大的最大利润返回
可以看到，时间复杂度O(n)=n^2;
当数据量最够大时，肯定超出时间限制
所以 我们选择使用动态规划解题
按照动态规划解题步骤：
1.设计状态
2.写出状态转移方程
3.设定初始状态
4.执行状态转移
5.返回最终的解
解题思路：
求出前缀最小值数组 premin[]
遍历一遍prices数组，在用prices[i]-premin[i-1]
找到两数组相减的最大值
为所求值
时间复杂度O(n)=n
根据前两课的训练，一个最小值数组对于我们毫无难度
premin[i]=min(premin[i-1],prices[i])
代码：
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int maxProfit(int* prices, int pricesSize){
int premin[pricesSize];
for(int i=0;i<pricesSize;i++)
{
if(i==0)
{
premin[i]=prices[i];
}
else
{
premin[i]=min(premin[i-1],prices[i]);
}
}
int ans=0;
for(int i=1;i<pricesSize;i++)
{
ans=max(ans,prices[i]-premin[i-1]);
}
return ans;
}
后缀最值
1299. 将每个元素替换为右侧最大元素
给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。
完成所有替换操作后，请你返回这个数组。
示例 1：
输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1] 解释：
- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1 示例 2：
输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。
根据题意，题解：
1.求出后缀最大值数组postmax
2.按照题意malloc一个ans数组
3.再将postmax数组中的值往ans数组中挪动
4.最后返回即可
状态转移方程：postmax[i]=max(postmax[i+1],arr[i])
代码：
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int* replaceElements(int* arr, int arrSize, int* returnSize){
*returnSize=arrSize;
int *ans=(int *)malloc(sizeof(int)*arrSize);
int postmax[arrSize];
for(int i=arrSize-1;i>=0;i--)
{
if(i==arrSize-1)
{
postmax[i]=arr[i];
}
else
{
postmax[i]=max(postmax[i+1],arr[i]);
}
}
for(int i=0;i<arrSize;i++)
{
if(i==arrSize-1)
ans[i]=-1;
else
ans[i]=postmax[i+1];
}
return ans;
}
前缀最值变形
1014. 最佳观光组合
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6]
输出：11
解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入：values = [1,2]
输出：2
链接: 最佳观光组合
思路：
1.由题意得 得分= values[i] + values[j] + i - j
2.可以分解为（values[i]+i）+(values[j]-j)
3.由因为 i<j 我们可以去求出 values[i]+i 的前缀最大值数组
4.然后 遍历数组values，设定一个初始值 ans=values[0]+values[1]+0-1;
5.且状态转移方程为 ans=max(ans,premax[j-1]+values[j]-j)
5.可以求出ans的最大值
代码：
int max(int a,int b)
{
return a>b?a:b;
}
int maxScoreSightseeingPair(int* values, int valuesSize){
int premax[valuesSize];
premax[0]=values[0];
for(int i=1;i<valuesSize;i++)
{
premax[i]=max(premax[i-1],values[i]+i);
}
int ans=values[0]+values[1]+0-1;
for(int j=1;j<valuesSize;j++)
{
ans=max(ans,premax[j-1]+values[j]-j);
}
return ans;
}
前缀+后缀 最值
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组[0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
这是一道leetcode的一道困难题，但只是一个纸老虎，练习了前几道题，掌握好解题方法，其实很简单。
根据前几题我们知道了求前缀最值数组和后缀最值数组
前缀最值数组：
void Premax(int *num,int sz,int *premax ){
for(int i=0;i<sz;i++)
{
if(i==0)
{ premax[i]=num[i];}
else
{
premax[i]=max(premax[i-1],num[i]);
}
}
}
后缀最值数组：
void Postmax(int *num,int sz,int *postmax)
{
for(int i=sz-1;i>=0;i--)
{
if(i==sz-1)
{
postmax[i]=num[i];
}
else
{
postmax[i]=max(postmax[i+1],num[i]);
}
}
}
解题思路：
1.要求接住的所有雨水sum
2.只要将 每根柱子上的雨水数量 加起来即可
3.求出前缀最大值数组和后缀最大值数组
4.当定位到 i柱子的时候，i柱子上的雨水数量
5.等于其左右两边柱子的高度的最大值中的较小值-自身柱子的高度
6.状态转移方程为 sum+=(min(premax[i],postmax[i])-height[i]);
代码如下：
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
void Premax(int *num,int sz,int *premax ){
for(int i=0;i<sz;i++)
{
if(i==0)
{ premax[i]=num[i];}
else
{
premax[i]=max(premax[i-1],num[i]);
}
}
}
void Postmax(int *num,int sz,int *postmax)
{
for(int i=sz-1;i>=0;i--)
{
if(i==sz-1)
{
postmax[i]=num[i];
}
else
{
postmax[i]=max(postmax[i+1],num[i]);
}
}
}
int trap(int* height, int heightSize){
int premax[heightSize];
int postmax[heightSize];
Postmax(height,heightSize,postmax);
Premax(height,heightSize,premax);
int sum=0;
for(int i=0;i<heightSize;i++)
{
sum+=(min(premax[i],postmax[i])-height[i]);
}
return sum;
}
这道leetcode的困难题就完成了，是不是纸老虎呢
结语
本期是动态规划的最后一期博客，动态规划的题还有很多，博主只是带大家简单的介绍了一下动态规划，还有待大家一起努力。
我是Tom-猫
如果觉得有帮助的话，记得
一键三连哦ヾ(≧▽≦*)o。
