Tagged Questions
0
votes
0answers
40 views
Dynamic Programming/LCS.Why is it defined in terms of suffix
I am reading about the DP version of the longest common substring from wiki:
It uses the formula:
LCS(p, q) = LCS(p - 1, q - 1) + 1 if X[p] == Y[q] ELSE
LCS(p, q) = 0
This is defined as the ...
0
votes
2answers
62 views
Suffix tries vs dynamic programming for string algorithms
It seems that many difficult string algorithms can be solved both using suffix tries(trees) and Dynamic Programming.
But I am not sure which approach is best to use and when.
Additionally which ...
1
vote
2answers
98 views
Break a string of characters into valid words
I am reading a problem on Dynamic Programming. The problem is the following:
Break a string of characters of length n into a sequence of valid
words. Assume that there is a datastructure that ...
0
votes
2answers
91 views
Can not understand knapsack solutions
In wikipedia the algorithm for Knapsack is as follows:
for i from 1 to n do
for j from 0 to W do
if j >= w[i] then
T[i, j] := max(T[i-1, j], T[i-1, j-w[i]] + v[i]) [18]
...
1
vote
2answers
77 views
Why does this DP solution for longest common subsequence work correctly?
Concerning the longest common subsequence problem, the basic algorithm as presented in all online resources is clear to me. This algorithm is described here:
What I am not clear is the algorithm ...
0
votes
1answer
145 views
Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array)
Pls help to solve this que.. does any one have DP solution for following que which uses either recursion..
Write a program to find all the possible paths from a starting point to dest point in a ...
1
vote
2answers
146 views
What are some good resources for learning backtracking, branch-and-bound and dynamic programming algorithms? [closed]
CLRS doesn't seem to cover bactracking/branch-and-bound. I tried several resources online, though I get the idead behind these, I am unable to write code for, let's say, Knapsack problem. So, I want ...
0
votes
0answers
158 views
Edit Distance variation
Going through "Introduction to algorithms" by "Cormen et al ", I came across a very popular question of dynamic programming named as "Edit Distance". While reading it and devising its solution I got ...
6
votes
8answers
440 views
Stable merging two arrays to maximize product of adjacent elements
The following is an interview question which I am unable to answer in a complexity less than an exponential complexity. Though it seems to be an DP problem, I am unable to form the base cases and ...
4
votes
3answers
291 views
How can I improve this algorithm to prevent TLE is SPOJ submission?
I am trying to solve the following problem:
http://www.spoj.pl/problems/TRIP/
I wrote a solution using DP in C++ (code posted below). But I get TLE. How can I optimize my code?
...
2
votes
2answers
141 views
Best Way to Save Results - Dynamic Programming
I am working to solve a problem that is a bit similar to Euler Problem 215. I think I can explain this without explaining the entire problem and/or my full approach to solving it.
Right now I'm ...
2
votes
1answer
136 views
Hash Table in r5rs
I am solving a problem on project euler requiring dynamic programming, and in this particular instance, it is cleaner to use a hash table over a dynamic programming "solutions" table. Using r5rs, what ...
1
vote
3answers
130 views
Data-structure to “map” collections to states in a dynamic-programming algorithm
I am coding for fun an algorithm to determine the best order of constructing N Building objects. Of course, each Building has its own characteristics (such as a cost, a production, a time of ...
13
votes
6answers
6k views
Dynamic programming practice problems with solutions
I have seen many questions on stackoverflow where dynamic programming technique can be used to make a exponential algorithm, a polynomial one. I have seen standard problems on dynamic programming. Is ...
