implement DP for a recursive function

Question

I have the following recursive function:

typedef unsigned long long ull;

ull calc(ull b, ull e)
{
  if (!b) return e;
  if (!e) return b;
  return calc(b - 1, e - 1) + calc(b - 1, e) - calc(b, e - 1);
}

I want to implement it with dynamic programming (i.e. using storage). I have tried to use a map<pair<ull, ull>, ull> but it is too slow also. I couldn't implement it using arrays O(1) too.

I want to find a solution so that this function solves quickly for large b, es.

I'm not sure I get the question right, so could you clarify what exactly do you want: do you want to get rid of the recursion, or do you just want to change the way you store data? — SingerOfTheFall
– SingerOfTheFall, Commented Jul 3, 2012 at 7:15
@SingerOfTheFall I understand recursion, but I want to speed this function up — user586399
– user586399, Commented Jul 3, 2012 at 7:17
The obvious optimization is to use a cache, possibly implemented as a hash map. — Philip
– Philip, Commented Jul 3, 2012 at 7:17
can't you do it this way DP[0][e] = e DP[b][0] = b and then DP[b][e] = DP[b-1][e-1] + DP[b-1][e] - DP[b][e-1] — sukunrt
– sukunrt, Commented Jul 3, 2012 at 7:17

MBo · Accepted Answer · 2012-07-05 19:34:34Z

5

Make a table b/e and fill it cell by cell. This is DP with space and time complexity O(MaxB*MaxE).

Space complexity may be reduced with Ante's proposal in comment - store only two needed rows or columns.

0 1 2 3 4 5
1 0 3 . . .
2 . . . . .
3 . . . . .
4 . . . . .

edited Jul 5, 2012 at 19:34

answered Jul 3, 2012 at 7:20

MBo

80.7k5 gold badges61 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user1168577 Over a year ago

beat me by about 15 seconds :).

Ante Over a year ago

It is enough to store current and last row or column. Space required is O(min(MaxB,MaxE)).

sukunrt · Accepted Answer · 2012-07-03 07:25:06Z

2

If a bottom up representation is what you want then this would do fine.

Fill up the table as MBo has shown

This can be done as:

for e from 0 to n:
  DP[0][e] = e
for b from 0 to n:
  DP[b][0] = b
for i from 1 to n:
   for j from 1 to n:
      DP[i][j] = DP[i-1][j-1] + DP[i-1][j] - DP[i][j-1]

now your answer for any b,e is simply DP[b][e]

answered Jul 3, 2012 at 7:25

sukunrt

1,54310 silver badges20 bronze badges

2 Comments

user586399 Over a year ago

DP[0][0] once == e and then == b ??

sukunrt Over a year ago

Both the times it's 0. Doesn't make a difference.

TemplateRex · Accepted Answer · 2012-07-03 07:21:04Z

2

You might want to take a look at this recent blog posting on general purpose automatic memoization. The author discusses various data structures, such std::map, std::unordered_map etc. Warning: uses template-heavy code.

answered Jul 3, 2012 at 7:21

TemplateRex

70.9k21 gold badges176 silver badges316 bronze badges

Comments

user1168577 · Accepted Answer · 2012-07-03 07:58:34Z

1

You can implement in O(n^2) (assuming n as max number of values for b and e ) by using a 2 dimensional array. Each current value for i,j would depend on the value at i-1,j and i-1,j-1 and i,j-1. Make sure you handle cases for i=0, j=0.

edited Jul 3, 2012 at 7:58

answered Jul 3, 2012 at 7:21

user1168577

1,98311 silver badges15 bronze badges

2 Comments

user586399 Over a year ago

Ok, if we look at b, e they can be in 3 cases: b > e, b < e, b == e. At 3 cases, we cannot guarantee that a value exists in DP[0][0]?

user1168577 Over a year ago

You are doing this bottom up so this condition won't happen. Can you explain with an example?

Collectives™ on Stack Overflow

implement DP for a recursive function

4 Answers 4

2 Comments

2 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related