New answers tagged

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