动态规划-买卖股票系列

121.买卖股票的最佳时机

Python:

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices)==0:
            return 0
        dp=len(prices)*[0]
      
       
        minprice=int(prices[0])
        
        for i in range (1,len(prices)):
            minprice=min(minprice,prices[i])
            dp[i]=max(dp[i-1],prices[i]-minprice)
            
        return dp[-1]

java:

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        
        int []dp=new int[n];
        int minpri=prices[0];
 
        for (int i=1;i
        {
            dp[i] = Math.max(dp[i-1],prices[i]-minpri);
            minpri=Math.min(prices[i],minpri);
        }
        return dp[n-1];
 
 
    }
}

121.买卖股票的最佳时机 II

Python:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n=len(prices)
        dp=[[0 for _ in range (2)] for _ in range(n)]
 
        dp[0][0]=0
        dp[0][1]=-prices[0]
 
        for i in range (1,n):
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
        return dp[-1][0]

Java:

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int [][] dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
 
        for (int i=1; i
        {
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
 
 
        }
        return dp[n-1][0];
 
    }
}

Python贪心算法：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res=0
        for i in range(1,len(prices)):
            if prices[i]>prices[i-1]:
                res+=(prices[i]-prices[i-1])
            else:
                continue
        return res