Converting recursive algorithm to DP

Question

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?

Answer 1

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.

Answer 2

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.