20 Nov 2016

Recursion to 2 dimensional dynamic programming II

文章欢迎转载,但转载时请保留本段文字,并置于文章的顶部
Author: derek0883@gmail.com
本文原文地址:http://www.gorecursion.com/algorithm/2016/11/20/2d-dynamic2.html

This article will show you how to use recursion method solve problem, then easily lead to a 2 dimensional dynamic programming solution.

Best Time to Buy and Sell Stock IV

Leetcode Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Before solve IV, you should solve those 3 problems first: 1. Leetcode Best Time to Buy and Sell Stock III 2. Leetcode Best Time to Buy and Sell Stock II 3. Leetcode Best Time to Buy and Sell Stock

Vide explanation:

For Best Time to Buy and Sell Stock II

As we can use as many transactions as you like, So the option is:

make transaction as long as you can make profit:

public int maxProfit(int[] prices) {
    return maxProfitII(prices, 0, 0);
}
private int maxProfitII(int[] prices, int pos) {
    int profit = 0;
    for (int i = pos+1; i < prices.length; i++) {
        int diff = prices[i] - prices[i-1];
        if (diff > 0)
            profit += diff;
    }
    return profit;
}

For Best Time to Buy and Sell Stock III

It is a special case of problem IV, when k is 2. We can use DFS or BFS

DFS O(n^2) time complexity solution

It is easy to get a DFS solution, each step, if you can get profit, then you have two options: 1. Use 1 transaction. 2. Don’t transact.

public int maxProfit(int[] prices) {
    return dfs(prices, 2);
}
private int dfs(int[] prices, int pos, int k) {
    if (k == 0 || pos == prices.length)
        return 0;
    int min = Integer.MAX_VALUE;
    int profit = 0;
    for (int i = pos; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        int diff = prices[i] - min;
        if (diff > 0) {
            diff += dfs(prices, i+1, k-1);
        }
        profit = Math.max(profit, diff);
    }
    return profit;
}

BFS O(n^2) time complexity solution

class Node {
    int pos, profit, k;
    Node(int pos, int profit, int k) {
        this.pos = pos;
        this.profit = profit;
        this.k = k;
    }
}
private int bfs(int[] prices, int k) {
    Queue<Node> q = new LinkedList<>();
    q.offer(new Node(0, 0, 0));
    int profit = 0;
    while (!q.isEmpty()) {
        Node n = q.poll();
        profit = Math.max(profit, n.profit);
        if (n.k == k || n.pos == prices.length)
            continue;
        int min = Integer.MAX_VALUE;
        for (int i = n.pos; i < prices.length; i++) {
            min = Math.min(min, prices[i]);
            int diff = prices[i] - min;
            if (diff > 0)
                q.offer(new Node(i+1, diff+n.profit, n.k+1));
        }
    }
    return profit;
}

Now we can move to Best Time to Buy and Sell Stock IV

DFS + memorize O(n x k) time complexity

We start from index 0, each step, we have 2 options: 1. if we can make profit, then we make transaction, we get profit with prices[i] - minimum prices of previous days, with k-1 left. 2. we don’t make transaction, just keep move index to the next.

private int dfsCache(int[] prices, int k) {
    int[][] cache = new int[k+1][prices.length];    
    for (int i = 0; i <= k; i++)
        Arrays.fill(cache[i], -1);
    int profit = dfsCache(prices, 0, k, cache);
    return profit;
}
private int dfsCache(int[] prices, int pos, int k, int[][] cache) {
    if (k == 0 || pos == prices.length)
        return 0;
    if (k >= prices.length-pos) // Version 2
        return maxProfitII(prices, pos);
    if (cache[k][pos] != -1)
        return cache[k][pos];
    int min = Integer.MAX_VALUE;
    int profit = 0;
    for (int i = pos; i < prices.length; i++) {
        min = Math.min(min, prices[i]);
        int diff = prices[i] - min;
        if (diff > 0)
            diff += dfsCache(prices, i+1, k-1, cache);
        profit = Math.max(profit, diff);
    }
    cache[k][pos] = profit;
    return profit;
}

DP O(n^2 x k) time complexity

private int dpV1(int[] prices, int k) {
    int[][] fn = new int[k+1][prices.length];

    for (int n = 1; n <= k; n++) {
        for (int i = 1; i < prices.length; i++) {
            int profit = 0;
            for (int j = i; j >= 0; j--) {
                profit = Math.max(profit, prices[i] - prices[j] + fn[n-1][j]);
            }
            fn[n][i] = Math.max(fn[n][i-1], profit);
        }
    }
    return fn[k][prices.length-1];
}

DP O(n x k) time complexity

private int dpV2(int[] prices, int k) {
    int[][] fn = new int[k+1][prices.length];

    for (int n = 1; n <= k; n++) {
        int max = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            fn[n][i] = Math.max(fn[n][i-1], max + prices[i]);
            max = Math.max(fn[n-1][i] - prices[i], max);
        }
    }
    return fn[k][prices.length-1];
}

DP O(n) space time complexity

Again, every time we see something like fn[i] = SomeOperation(fn[i-1]), it means we don’t have to save the entire array, we just need save previous result, we can copy or we can swap object reference, fn1 and fn2

private int dpV4(int[] prices, int k) {
    int[] fn1 = new int[prices.length];
    int[] fn2 = new int[prices.length];
    
    for (int n = 1; n <= k; n++) {
        int max = -prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            fn2[i] = Math.max(profit, max + prices[i]);
            max = Math.max(fn1[i] - prices[i], max);
            profit = fn2[i];
        }
        // Copy, or we can swap object reference, fn1 and fn2
        for (int i = 0; i < prices.length; i++)
            fn1[i] = fn2[i];
    }
    return fn2[prices.length-1];
}
Better solution would be, flip index
private int dpV5(int[] prices, int k) {
    int[][] fn = new int[2][prices.length];

    int idx = 1;
    for (int n = 1; n <= k; n++) {
        int max = -prices[0];
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            fn[idx][i] = Math.max(profit, max + prices[i]);
            max = Math.max(fn[idx^1][i] - prices[i], max);
            profit = fn[idx][i];
        }
        idx = (~idx)&1;
    }
    return fn[(~idx)&1][prices.length-1];
}