欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划---买卖股票的最佳时机(LeetCode 70)

程序员文章站 2022-07-16 10:18:30
...

1.问题描述:

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
实例1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

实例2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

2.解题思路:

步骤一设置dp[i]含义是price[i]及之前最低的买入值。 先按照题目所问的,假设dp[i]表示price[0]price[i]的元素们并且以price[i]结尾的最大利润,再看dp[0]表示一个元素的最大利润,所以最基础的子结构是一个元素。因此,dp[i]去掉一层子结构(即一个元素)为dp[i-1],得到dp[i]的前一个状态为dp[i-1],这肯定是没有问题的。

但是,你想想,price[0]price[i]的元素们并且以price[i]结尾的最大利润,是建立在price[0]price[i-1]的元素们并且以price[i-1]结尾的最大利润的基础上吗?显然不是的,这完全说不同,公式是根据动态规划的最优子结构特性得到的,肯定每错,所以我们要转换思路。

想一想利润能等价转换成什么? 利润 = 卖出 - 买入, 卖出的是price[i],最低的买入值我们不知道,那如果我们将dp[i]设置成price[i]及之前最低的买入值,可不可以?
咦,好像非常合理,是吧,这样dp[i]的值最低买入可能来自于dp[i-1]

步骤二状态转换方程
①从哪里来:通过上面的分析,我们知道dp[i]可能来自dp[i-1],这是price[0]price[i-1]的元素们中最小的值,而新增加的price[i]也可能是买入的最小值,所以,dp[i]应该是他们之间的最小值。
②状态转换方程: dp[i] = min(dp[i-1], prices[i])

步骤三:**初始值。**由状态转换方程可知,dp[i]只与dp[i-1]prices[i]有关,prices[i]知道,dp[i-1]可能不知道,一直倒推下去,就是dp数组的最左边的元素,dp[0]需要赋初值。

代码:

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i]为从元素0-i,最小的数
        int m = prices.length;
        if (m <= 0)
            return 0;
        int[] dp = new int[m];
        int max = 0;       //题目要求不能盈利返回0,所以这里初值设置0而不是Integer.MIN_VALUE
        int temp = 0;
        //设置初始值
        dp[0] = prices[0];
        // dp[i] = min(dp[i-1], prices[i])
        for (int i = 1; i < m; i++) {
            dp[i] = Math.min(dp[i-1], prices[i]);
            if (dp[i] != prices[i]) {
                temp = prices[i] - dp[i];
                if (temp > max)
                    max = temp;
            }
        }
        return max;   
    }
}

3.空间优化:

一般,dp用数组的大多数都是可以进行空间优化的,我们来看看能不能优化?
dp[i]只与dp[i-1]prices[i]有关,也就是说,在计算dp[i]的时候,dp[0]dp[1]dp[i-2]都不需要,只需要dp[i-1]prices[i],而prices[i]已知,那么我们只需要设置一个变量,每次保存一下dp[i-1]

优化后运行时间提高了25%
动态规划---买卖股票的最佳时机(LeetCode 70)
优化后代码如下:

class Solution {
    public int maxProfit(int[] prices) {
        // dp[i]为从元素0-i,最小的数
        int m = prices.length;
        if (m <= 0)
            return 0;
        //设置初始值
        int dp = prices[0];
        int max = 0;       //题目要求不能盈利返回0,所以这里初值设置0而不是Integer.MIN_VALUE
        int temp = 0;
        // dp[i] = min(dp[i-1], prices[i])
        for (int i = 1; i < m; i++) {
            dp = Math.min(dp, prices[i]);
            if (dp != prices[i]) {
                temp = prices[i] - dp;
                if (temp > max)
                    max = temp;
            }
        }
        return max;   
    }
}
相关标签: 动态规划