20 Nov 2016

# Recursion to 2 dimensional dynamic programming II

Author: derek0883@gmail.com

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

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:

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;
}
``````

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) {
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];
}
``````