6. 动态规划

435 Non-overlapping Intervals (Medium)

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

• 可以认为区间的终点总是大于它的起点。
• 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

121 best-time-to-buy-and-sell-stock(Easy)

给定一个数组，它的第 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。

题解：
首先很容易能想到暴力解法是：

• 定义最大利润max
• 针对prices[i]，在剩余的价格中寻找prices[j]，使得prices[j] - prices[i]最大
• 更新max = max(max, prices[j] - prices[i])

只不过这种解决的时间复杂度为，除非面试官要求你用高复杂度的方法实现，这个代码千万不要拿出来。
实现如下：

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length; i ++) {
            for (int j = prices.length - 1; j > i; j --) {
                max = Math.max(max, prices[j] - prices[i]);
            }
        }
        return max;
    }
}

尝试使用动态规划：此题可以转换为寻找第i天使交易利润最大，而第i天利润最大即是第i - 1天最大利润与prices[i] - minPrice的较大值。

• minPrice记录前i-1天的最小价格
• maxProfit记录前i-1天的最大利润
• 更新maxProfit，Math.max(max, prices[i] - minPrice)

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int minPrice = prices[0];
        for (int i = 0; i < prices.length; i ++) {
            minPrice = Math.min(prices[i], minPrice);
            maxProfit = Math.max(max, prices[i] - minPrice);
        }
        return maxProfit;
    }
}

DP注意事项：

• 分析原问题与子问题的关系
• 确定初始条件
• 确定迭代条件即状态转移方程，如上题中：第i天最大收益 = max(i-1天最大收益, 第i天的价格-前i-1天中的最小价格)
• 处理特殊情况（如有）