leetcode【121-买卖股票的最佳时机】思考、优化、改进

曾经终败给现在 2023-01-10 10:26 110阅读 0赞

**\# leetcode【121-买卖股票的最佳时机】思考、优化、改进  
 声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！**

这个题一看题目，需要遍历所有项并且每层遍历第i项之前的所有项，时间复杂度O(n²)，最后再次遍历选最大值。  
     这种问题是很标准的动态规划问题，问题在于如何确定状态转移方程。确定dp\[i\]所表示的含义。设置好初值  
    我一直认为动态规划的状态转移方程与数学归纳法有着千丝万缕的联系，dp\[i+1\]由已知的前几项递推得来。  
这里会比较自然的想到**设置dp\[i\]代表第i天卖出时候可获得的最大利润**，

for j in range(0,i)#主要是写逻辑..用了句python
    if(price[i]>price[j])
     dp[i] = max(dp[i],dp[j]+price[i]-price[j]);//找最大的

再设置好初始化：  
dp\[i\]初始化皆为0,返回dp\[i\]中最大的  
上一下代码：

int maxProfit(vector<int>& prices) { 
            vector<int> dp(prices.size(),0);
            int res= 0;
            for(int i=1;i<prices.size();i++)
                { 
                for(int j=0;j<i;j++)
                if(prices[i]>prices[j])
                    dp[i] = max(dp[i],dp[j]+prices[i]-prices[j]);
                if(dp[i]>res)
                    res = dp[i];
                }
            return res;
        }

逻辑是没有问题的，但是提交到leetcode上发现超出时间限制了，测试用例是一串超长的文本，所以我们要再优化。DP的常用优化方法无疑是状态压缩，这个状态压缩真的思考了很久，但是还是没想出来。\*\*仔细观察：我们在遍历到第i项时候，dp\[i\]取决于什么呢？其实是取决于0~i中最低价（设为minprice），我们dp\[i\]一定price\[i\]-minprice(0,i)\*\*我们只需维护两个变量，一个是利润的最大值，一个是价格的最小值，直接上代码:

int maxProfit(vector<int>& prices) { 
            int inf = 1e9;
            int minprice = inf, maxprofit = 0;
            for (int price: prices) { 
                maxprofit = max(maxprofit, price - minprice);
                minprice = min(price, minprice);
            }
            return maxprofit;
        }

这种方法只需遍历一遍，维护两个变量，相当方便，又一次启发了我的思路。