算法day35-动态规划（8）

目录

•  买卖股票的最佳时机
  
• 买卖股票的最佳时机II
  
• 买卖股票的最佳时机III
  

一、买卖股票的最佳时机

 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=problem-list-v2&envId=8At1GmaZ

• 状态定义：
  
  
  
  • 使用一个二维数组 dp[0] 表示在第 i 天持有股票时的最大收益。
    
  • 使用 dp[1] 表示在第 i 天不持有股票时的最大收益。
    
  
  
• 初始条件：
  
  
  
  • 在第 0 天，如果持有股票，最大收益是 -prices[0]（即买入股票的花费）。
    
  • 在第 0 天，如果不持有股票，最大收益是 0（即没有操作）。
    
  
  
• 状态转移：
  
  
  
  • 对于每一天 i（从 1 到 length - 1），有两种选择：
    
    
    
    • 持有股票：可以选择继续持有前一天的股票，或者在今天再次买入股票（此时的收益为 -prices），即 dp[0] = Math.max(dp[i-1][0], -prices)。
      
    • 不持有股票：可以选择继续不持有前一天的股票，或者在今天卖出股票（此时的收益为 dp[i-1][0] + prices），即 dp[1] = Math.max(dp[i-1][1], dp[i-1][0] + prices)。
      
    
    
  
  
• 最终结果：
  
  
  
  • 在最后一天（第 length-1 天），我们关心的是不持有股票的最大收益，即 dp[length-1][1]。
    
  
  

时间复杂度：

该算法的时间复杂度为 O(n)，其中 n 为股票价格数组的长度，因为只需要遍历一次数组。
空间复杂度：

该算法的空间复杂度为 O(n)，主要是由 dp 数组占用的空间决定。
[code]class Solution {    public int maxProfit(int[] prices) {        //dp[0]持有股票得到的最大收益，dp[1]不持股最大收益        if(prices == null || prices.length == 0)    return 0;        int length = prices.length;        int[][] dp = new int[length][2];        dp[0][0] = -prices[0];        dp[0][1] = 0;        for(int i=1; i