代码随想录算法训练营 动态规划part11

一、买卖股票的最佳时机III  

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

请选一个喜欢的吧/(ㄒoㄒ)/~~123. 买卖股票的最佳时机 III - 力扣（LeetCode）

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int n = prices.length;
        //定义二维数组，5种状态  
        int[][] dp = new int[n][5];
        //初始化第一天的状态
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i=1;i<n;++i) {
            //dp[i][0]相当于初始状态，它只能从初始状态转换来
            dp[i][0] = dp[i-1][0];
            //处理第一次买入、第一次卖出
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+prices[i]);
            //处理第二次买入、第二次卖出
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-prices[i]);
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+prices[i]);
        }
        //返回最大值
        return Math.max(Math.max( Math.max(dp[n-1][0],dp[n-1][1]),Math.max(dp[n-1][2],dp[n-1][3]) ),dp[n-1][4]);
    }
}
 
 

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        return dfs(0,0,0,k,prices);
    }
    //计算k次交易，index表示当前是哪天，status是买卖状态，coutnt为交易次数
    private int dfs(int index, int status, int count, int k, int[] prices) {
        if(index==prices.length || count==k) {
            return 0;
        }
        int a=0,b=0,c=0;
        //保持不动
        a = dfs(index+1,status,count,k,prices);
        if(status==1) {
            //卖一股，并将交易次数+1
            b = dfs(index+1,0,count+1,k,prices)+prices[index];
        } else {
            //买一股
            c = dfs(index+1,1,count,k,prices)-prices[index];
        }
        return Math.max(Math.max(a,b),c);
    }
}