LeetCode 188. 买卖股票的最佳时机 IV(动态规划)(递归)

 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (k == 0 || prices.size() == 0) {
            return 0;
        }
        return DFS(0, 0, 0, k, prices);
    }
    //计算k次交易，index表示当前是哪天，status是买卖状态，coutnt为交易次数
    int DFS(int index, int status, int count, int k, vector<int>& prices) {
        if (index == prices.size() || count == k) {
            return 0;
        }
        int keep = 0, sell = 0, buy = 0;
        //保持
        keep = DFS(index + 1, status, count, k, prices);
        if (status == 1) {
            //卖出
            sell = DFS(index + 1, 0, count + 1, k, prices) + prices[index];
        }
        else {
            //买入
            buy = DFS(index + 1, 1, count, k, prices) - prices[index];
        }
        return max(max(keep, sell), buy);
    }
};

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int n = prices.length;
        //当k非常大时转为无限次交易
        if(k>=n/2) {
            int dp0=0,dp1=-prices[0];
            for(int i=1;i<n;++i) {
                int tmp = dp0;
                dp0 = Math.max(dp0,dp1+prices[i]);
                dp1 = Math.max(dp1,dp0-prices[i]);
            }
            return Math.max(dp0,dp1);
        }
        Map<Key,Integer> cache = new HashMap<Key,Integer>();
        return dfs(cache,0,0,0,k,prices);
    }

    //带记忆化的 计算k次交易，代码和递归版的一样只是前后加了缓存
    private int dfs(Map<Key,Integer> cache, int index, int status, int count, int k, int[] prices) {
        Key key = new Key(index,status,count);
        if(cache.containsKey(key)) {
            return cache.get(key);
        }
        if(index==prices.length || count==k) {
            return 0;
        }
        int a=0,b=0,c=0;
        a = dfs(cache,index+1,status,count,k,prices);
        if(status==1) {
            b = dfs(cache,index+1,0,count+1,k,prices)+prices[index];
        } else {
            c = dfs(cache,index+1,1,count,k,prices)-prices[index];
        }
        cache.put(key,Math.max(Math.max(a,b),c));
        return cache.get(key);
    }
    //Key对象封装了index、status、交易次数count，作为map的key
    private class Key {
        private final int index;
        private final int status;
        private final int count;
        Key(int index,int status,int count) {
            this.index = index;
            this.status = status;
            this.count = count;
        }
        //这里需要实现自定义的equals和hashCode函数
        public int hashCode() {
            return this.index + this.status + this.count;
        }
        public boolean equals(Object obj) {
            Key other = (Key)obj;
            if(index==other.index && status==other.status && count==other.count) {
                return true;
            }
            return false;
        }
    }
}