22 Nov 2016

# Recursion to 3 dimensional dynamic programming I

Author: derek0883@gmail.com

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

## K Sum

Lintcode K Sum

Given n distinct positive integers, integer k (k <= n) and a number target.

Find k numbers where sum is target. Calculate how many solutions there are?

Example Given [1,2,3,4], k = 2, target = 5.

There are 2 solutions: [1,4] and [2,3].

Return 2.

### DFS + memorize O(n x k x target) time complexity solution

Index i start from 0, there are 2 options on each steps: 1. use value of A[i], then we are looking for: target - A[i] with k-1 numbers. 2. do not use value of A[i], then still looking for target with k numbers.

From recursion tree, we know we need a 3 dimentional array to store the results.

``````private int dfsCache(int A[], int k, int target) {
int[][][] cache = new int[k+1][A.length][target+1];
for (int i = 0; i <= k; i++) {
for (int j = 0; j < A.length; j++)
Arrays.fill(cache[i][j], -1);
}
return dfsCache(A, 0, k, target, cache);
}

private int dfsCache(int A[], int pos, int k, int target, int[][][] cache) {
if (target == 0 && k == 0)
return 1;
if (target < 0 || k <= 0 || pos+k > A.length)
return 0;
if (cache[k][pos][target] != -1)
return cache[k][pos][target];
int nWay = dfsCache(A, pos+1, k, target, cache);
nWay += dfsCache(A, pos+1, k-1, target - A[pos], cache);
cache[k][pos][target] = nWay;
return nWay;
}
``````

### DP O(n x k x target) time complexity

From recursion tree, we know it is a 3 dimentional bottom up DP problem.

``````private int dpV1(int A[], int k, int target) {
int[][][] fn = new int[k+1][A.length+1][target+1];
for (int i = 0; i <= A.length; i++)
fn[i] = 1;

for (int i = 1; i <= k; i++) {
for (int j = 1; j <= A.length; j++) {
for (int t = 1; t <= target; t++) {
fn[i][j][t] = fn[i][j-1][t];
int use = t - A[j-1];
if (use >= 0)
fn[i][j][t] += fn[i-1][j-1][use];
}
}
}
return fn[k][A.length][target];
}
``````

### DP O(n x target) space complexity

Again, we can see every time, we move i to next, we only need access fn[i-1], this means we can reduce space complexity. the time complexity still 3 dimensional, but space complexity reduced to 2D

``````private int dpV2(int A[], int k, int target) {
int[][][] fn = new int[A.length+1][target+1];
for (int i = 0; i <= A.length; i++)
fn[i] = 1;

int ki = 1;
for (int i = 1; i <= k; i++) {
Arrays.fill(fn[ki], 0);
for (int j = 1; j <= A.length; j++) {
Arrays.fill(fn[ki][j], 0);
for (int t = 1; t <= target; t++) {
fn[ki][j][t] = fn[ki][j-1][t];
int use = t - A[j-1];
if (use >= 0)
fn[ki][j][t] += fn[ki^1][j-1][use];
}
}
ki = (~ki)&1;
}
return fn[(~ki)&1][A.length][target];
}
``````

### DP O(n x k) space complexity

Or we can start from 1 to length of array as outer loop, we can reduce space complexity to O(n x k)

``````private int dpV3(int A[], int k, int target) {
int[][][] fn = new int[k+1][target+1];
for (int i = 0; i <= 1; i++)
fn[i] = 1;

int ji = 1;
for (int j = 1; j <= A.length; j++) {
for (int i = 1; i <= k; i++) {
for (int t = 1; t <= target; t++) {
fn[i][ji][t] = fn[i][ji^1][t];
int use = t - A[j-1];
if (use >= 0)
fn[i][ji][t] += fn[i-1][ji^1][use];
}
}
ji = (~ji)&1;
}
return fn[k][(~ji)&1][target];
}
``````