New answers tagged dynamic-programming
1
Lets deal with the issues one at a time, since there are a few of them.
Problem 1
Take a look at those lines of code:
trow = [0] * (m+1)
table = [trow] * (n+1)
srow = [""] * (m+1)
solution = [srow] * (n+1)
The problem with this code, is that the same list is being placed a few times. This means, that every list in $table$ must be all ...
1
Programming questions are off-topic here.
Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try:
table = [[0]*(m+1) for j in range(n+1)]
solution = [ ["" for i in range(m+1)] for j in range(n+1) ]
Moreover, the returned string should be solution[n][m] and not solution[n-1][...
0
To use dynamic programming, you need to choose the order in which you fill in values for the vertices. The correct order is a topologically sorted order (any other order won't work). So, the two solutions are in some sense equivalent. Any solution is likely to use both components: topological sorting to determine the order to enumerate the vertices, and ...
2
When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.
For general $K$, your function is a known extension of the ...
2
If $c$ doesn't have too many factors and is not too large, the following should work reasonably well for typical numbers.
Factor $c$ into its prime factorization, say $c=p_1^{e_1} \cdots p_k^{e_k}$. Enumerate all tuples $(f_1,\dots,f_D)$ of non-negative integers such that $f_1 \cdots f_D = c$. For each such tuple $(f_1,\dots,f_D)$, and each $i$, find the ...
1
I believe this can be solved in $O(nm)$ time using dynamic programming:
$$\begin{align*}
B[i,k] &= A[i,k] + \dots + A[i,k+r-1] + C[i,r]\\
C[i,k] &= \max(A[i,k] + C[i,k+1], \max_{i'} B[i',k])
\end{align*}$$
Note that you can compute $A[i,k] + \dots + A[i,k+r-1]$ in $O(1)$ time as the difference of two prefix sums (assuming you have done a one-time ...
Top 50 recent answers are included
