I know there are a lot of already existing questions about this problem, but I haven't found anything that answers mine. My recursion is working fine for lower numbers (I tried int 10) but when I expand it to 100, it becomes exactly one step lower than it should. Not sure why.
My code:
public BigDecimal distinctLadderPaths(int rungs) {
if (rungs < 0)
throw new ArithmeticException("Ladders can't have negative rungs."); // if negative, throw exception
else if (rungs == 0)
return BigDecimal.valueOf(0); //if zero, return zero
else if (rungs <= 2)
return BigDecimal.valueOf(rungs); //if 1 or 2, return 1 or 2, respectively
else{
long[] f = new long[(rungs + 1)]; //create long Array for memory (f for fibonacci)
f[0] = 0; //1 steps
f[1] = 1; //2 steps
for(int i = 2; i <= rungs; i++) { //loop
f[i] = f[i - 1] + f[i - 2]; //at each step in the loop, add 1 step lower and 2 steps lower from the number of iterations
}
return BigDecimal.valueOf(f[rungs]); //return fibonacci value at final step of the rungs as BigDecimal
}
}
test code:
@Test
public void testDistinctLadderPaths100 (){
int rungs = 100;
BigDecimal expected = new BigDecimal("573147844013817084101");
BigDecimal result = lp.distinctLadderPaths(rungs);
assertEquals(expected, result);
}
I'm told the output should be 57314784401381708410
, but I'm getting 3736710778780434371
(which is the fibonacci number at the 99th step). Any ideas why?
fibonacci seq starts from 1. Sequence is 1, 1, 2, 3, 5, 8.. so initallize f[0] = f[1] = 1;