Solving Space-Time in Dynamic Programming

edisonnpebojot profile image Edison Pebojot(👨‍💻) ・2 min read

This is about my next article about dynamic programming. But I need your help. The drawback of Dynamic Programming is that it is possible to define the problem at hand as the optimal control problem.

The spectrum of such issues is remarkably wide, that is, the space it takes to store the data. With regards to restricting dynamic programming, the difficulty will be the amount of separate sub-problems you address in the code.

Often the difficulty is so high that the time constraint does not go in. Under that case, I would need to optimize it. For example, assumed the multiplication of the Matrix chain fell into that group.

However, I use a matrix or a hash table; this is because both give O(1)O\lparen 1\rparen lookup time. The time complexity can be raised from exponential time O(2n)O\lparen 2^{n}\rparen to psuedo-polynomial time complexities O(N×W)O\lparen N \times W\rparen .

Note: It also means that if my Knapsack capacity WW is a constant, or bounded by a polynomial in NN , the dynamic program is polynomial time.

But I need to optimize it from psuedo-polynomial time O(N×W)O\lparen N \times W\rparen to logarithmic time complexities O(log n)O\lparen log \space n\rparen .

For Example, I have a Knapsack Problem solved in Dynamic Programming approach which took polynomial time complexities O(N×W)O\lparen N \times W\rparen in both space and time:

function knapsackDP(index, weights, values, target, matrixDP) {
    var result = 0;
    // DP Part:
    if (matrixDP[index + "-" + target]) {
        return matrixDP[index + "-" + target];
    if (index <= -1 || target <= 0) {
        result = 0;
    } else if (weights[index] > target) {
        result = knapsackDP(index - 1, weights, values, target, matrixDP);
    } else {
        var current = knapsackDP(index - 1, weights, values, target, matrixDP),
            currentPlusOther = values[index] + knapsackDP(index - 1, weights, values, target - weights[index], matrixDP);
        result = Math.max(current, currentPlusOther);
    matrixDP[index + "-" + target] = result;
    return result;

var weights = [1, 2, 4, 2, 5],
    values = [5, 3, 5, 3, 2],
    target = 10;
knapsackDP(4, weights, values, target, {});
Enter fullscreen mode Exit fullscreen mode

But in terms of functional constraints, DP requires a lot of storage power, which often expands rapidly with the vector space dimension. (😅)

Posted on by:

edisonnpebojot profile

Edison Pebojot(👨‍💻)


I started using computers and writing software around 2008 and 2009, I taught myself Programming. However, I wasn't a typical "nerd-klutz". 😅


Editor guide

How you write math equations in dev.to?


ow, what I use is Katex (katex.org/)