• + 2 comments

    I solved it with recursion. Probably stupid but the problem is defined recursively so it was the first thing that popped in my mind. If you memoize the recursive calls it needn´t be terribly inefficient.

    • + 1 comment

      Can you post your recursive solution, please.

      • + 1 comment
        public static BigInteger fiboMod(BigInteger t1,BigInteger t2,int n){
                n = n-1;
                if(n == 1){
                    return t2;
                }
                return fiboMod(t2,t2.pow(2).add(t1),n);
            }
        • + 0 comments

          This is not DP. Its plain Recursion.

    • + 1 comment

      The point of doing it in DP and not in recursion is that recursion takes a lot of time while DP doesnt. Doesnt make any sense doing it in recursion as it is said to do it in dp.

      • + 0 comments

        Yes, but memoized recursion can give similar results to DP with only slight overhead (e.g. here).