# Solving Space-Time in Dynamic Programming

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\lparen 1\rparen$ lookup time. The time complexity can be raised from exponential time $O\lparen 2^{n}\rparen$ to psuedo-polynomial time complexities $O\lparen N \times W\rparen$ .

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

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

For Example, I have a Knapsack Problem solved in Dynamic Programming approach which took polynomial time complexities $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, {});


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:

### 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". 😅

### Discussion

How you write math equations in dev.to?

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