22 Nov 2016

Recursion to 3 dimensional dynamic programming I

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

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.

Video explanation

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[0][i][0] = 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[2][A.length+1][target+1];
    for (int i = 0; i <= A.length; i++)
        fn[0][i][0] = 1;

    int ki = 1;
    for (int i = 1; i <= k; i++) {
        Arrays.fill(fn[ki][0], 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][2][target+1];
    for (int i = 0; i <= 1; i++)
        fn[0][i][0] = 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];
}