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

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%

优化后代码如下：

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;   
    }
}