Dynamic Dynamic-Programming

How do we improve the memory usage of a dynamic programming algorithm

Dynamic Programming (DP) is an incredibly useful paradigm that allows for the solution of many NP-Complete problems in pseudo-polynomial time. By breaking up problems into their subproblems we can solve each subproblem once and store its result, hence removing the need for the computation of overlapping sub-problems.

The main benefit of DP is the trade-off of memory space vs time. A lot of computation time is saved by storing the results of previous computation. However, most DP applications, especially “bottom up” DP solutions use far more memory than is actually required. As it unknown before runtime what subproblems will need to be solved, the standard approach taught in most colleges and applied by most programmers involves allocating an n-dimensional array that can store the results of all subproblems. This however is unnecessary.

Each subproblem in a dp solution is identified by some group of parameters. By abstracting these groups of parameters to a state data type that can represent and identify each subproblem, we can use more effective data structures than static arrays.

An example C++ struct for the subset sum problem might be

struct state{
    int cur_element;
    int running_sum;
};

Each subproblem in the DP solution to the subset sum problem is represented by the current element under consideration, and the sum of elements used so far.

By implementing comparators for our data type we can allow it to be used by standard library data structures such as the C++ std::map

struct state{
    int cur_element;
    int running_sum;

    bool operator < (state rhs) const {
        if(cur_element!=rhs.cur_element) return cur_element < rhs.cur_element;
        return running_sum < rhs.running_sum;
    }

    bool operator == (state rhs) const {
        return (cur_element==rhs.cur_element&&running_sum==rhs.running_sum);
    }
};

There are many ways to use this abstracted idea of state to store the DP subproblem solutions more efficiently. For example you could use them as keys in a binary search tree (such as std::map). This would add a factor of log(#states) to your algorithmic efficiency, but it will ensure that the minimum required memory will be used.

Another option is to create or adapt a hashing function for your state data type to allow for amortised O(1) insertion and lookup.