【再谈动态规划】

前缀最值

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。