1
$\begingroup$

As a follow-up to this question , I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests.

int solve(int i, int crane1_pos, int crane2_pos, int dist)
{

    if(i == n)
    {
        return dist;
    }

    int dist1 = dist + get_dist(crane1_pos, t[i].first);
    int dist2 = dist + get_dist(crane2_pos, t[i].first);

    return min(solve(i + 1, t[i].second, crane2_pos, dist1), solve(i + 1, crane1_pos, t[i].second, dist2));

}

Where, get_dist is a function that looks like this:

int get_dist(int crn_pos, int fin_pos)
{
    if(crn_pos == -1)
        return 0;

    return abs(crn_pos - fin_pos);
}

$t$ in this particular situation is a vector of pair<int, int>, $n$ is the size of this vector and the initial call of the function is solve(0, -1, -1, 0).

I'm pretty sure this could be further improved by using DP, but upon doing some research on this issue, I found that I'm unable to transform this recurrence into some form of dynamic programming. I've derived the recurrence trees for several examples and I can't find the overlapping subproblems and a way to use memoization.

So I guess my question is, how do you turn this recurrence into DP?

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of cs.stackexchange.com/q/2057/755 - what do you think? $\endgroup$ – D.W. Dec 12 '16 at 3:43
  • $\begingroup$ @D.W. Indeed, those answers summarize the connections between the approaches. $\endgroup$ – Hendrik Jan Dec 12 '16 at 9:07
  • 2
    $\begingroup$ You don't "turn" your algorithm into "DP". Either your recursion is a DP recursion, or it is not. In the first case, simly add memoization. In the latter, you have to go back to thinking and come up with a whole different way of solving the problem. $\endgroup$ – Raphael Apr 12 '17 at 19:11
  • $\begingroup$ For anybody else looking for similar, see blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html $\endgroup$ – Simes Sep 17 '17 at 8:15
2
$\begingroup$

Didn't look at your code, but in general there are two important points that distinguish recursion from dynamic programming.

First recursion is top-down (starting with the big instances, by decomposing them into smaller instances and combining the answers) while DP is bottom-up (first solving the small cases, and combining them into larger ones).

The second important point is the table that contains the solutions to instances with certain parameters. This is to avoid computing certain cases more than once (as recursion tends to do).

So DP is upside down recursion in general. But one can also start with recursion and a lookup table that tests whether a certain subproblem was already solved.

$\endgroup$
1
$\begingroup$

In general for dynamic programming finding the recurrence is the most difficult part. You already have that!

Now you need to use something called memoization. You need to not do work that you've already done. So you'll need to create a matrix that your subproblems will fit into. Now, you need to have an if statement that checks if you've calculated a specific instance of this recurrence or not.

To more easily understand this, think about a recurrence for the Fibonacci sequence. The recurrence without memoization is exponential while using memoization it's linear!

To learn dynamic programming I used mitopencourseware videos on YouTube. Eric Demaine is a great teacher.

$\endgroup$
  • $\begingroup$ Yup, I'm pretty familiar with DP and the theory behind it, solved quite a few problems using said approach, but I've hit a roadblock while looking for what data to store for further use. It may be that the way I've solved this problem doesn't have the optimal substructure property. $\endgroup$ – user43389 Dec 14 '16 at 10:24
  • $\begingroup$ Store the optimal distance for [i,pos1,pos2] for suitable positions pos1 and pos2. $\endgroup$ – Hendrik Jan Dec 16 '16 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.