Hello everyone,

I have a problem with an assignment. In this assignment I had to create a program which needs to calculate how many different possibilities are there to get from number a to b. To get from a to b you can only D(double) the value or I(increment) the value.

For example a=3 & b=14 you will get:
Code:
DII = 3*2*2+2 = 14
DID = ((3*2)+1)*2 =14
DIIIIIIII = 3*2+8 =14
IDIIIIII=(3+1)*2+6=14
IIDIIII =(3+2)*2+4=14
IIIDII =(3+3)*2+2=14
IIIID =(3+4)*2+0=14
IIIIIIIIIII=3+11=14
This will give me 8 possibilities.

In my current solution I'm using a breadth-first search (BFS) to calculate all the possibilities only this is very slow, because sometimes there are many possibilities and with BFS you will go through all of them. So for example if want to calculate a=10 and b=1000, this will give me 74,116,423 possibilities.

I know a better solution, because people who also did this exercise told me their solution, but I do not understand it.

They used a counting solution. :
Count: (a,b) = (a+1,b) + (2a,b)
Store in table/dictionary

I also asked it in stackoverflow, where I got the same answer:
Answer.jpg

What I understand of this solution is as follows:
Code:
a=3 and b=14 
So a[3] += a[3+1] + a[3*2]; will give 2
a[4] += a[4+1] + a[4*2]; will give 2 
a[5] += a[5+1] + a[5*2]; will give 2 
a[6] += a[6+1] + a[6*2]; will give 3 
a[7] += a[7+1] + a[7*2]; will give 2
But the sum of the a's is 11. So I'm doing something wrong, but I can’t figure out what it is.

I hope that someone could tell me what I'm doing wrong.


With kind regards,

Danique