Dynamic programming

general
,
1

using dynamic programming helps to reduce the time complexity of my recursive algorithm. how this actually happens?
Is it possible to find factorial in less time with dynamic programming?
(the largest value of the output is 10^14)

2

As far as i know there is no Dynamic Programming solution for finding factorials. You can look at this post for finding factorial of large numbers.

2 Likes
3

If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function

does not have side effects and
does only depend on its parameters (i.e. not on some state).
It will save you time if (and only if) the function is called with the same parameters over and over again. Popular examples include the recursive definition of the Fibonacci numbers, that is

f(0)=0

f(1)=1

f(n+2)=f(n+1)+f(n), n≥0

When evaluated naively, ff is called exponentially often. With memoisation, f(n)f(n) has always been computed by f(n+1)f(n+1) already, thus only a linear number of calls remains.

1 Like
4

And for factorial here’s the code

#include <cstring>

#include
#include
#define ll long long
using namespace std;

int result[1000] = {0};

ll fact_dp(int n)

{

if (n >= 0) 
{
    result[0] = 1;
    for (int i = 1; i <= n; ++i) 
    {
        result[i] = i * result[i - 1];
    }
    return result[n];
}

}

5

@neget I don’t think you will be able to store the factorial of number like 10^14 since even Python can’t also store/calculate it! Btw you can also look here : http://stackoverflow.com/questions/26989075/approaching-dynamic-programming

@only4 Memory Saving Tip: You don’t need the whole array. You could just use two variables for calculating the factorial.

1 Like
6

@only4 your program fails for larger values. Even after changing ints to long long it works only till 20.

7

@nikhil_chandak
Yes but I think calling the function again and again takes more time than this, so this is time efficient. Please correct me if I am wrong.

8

I don’t think finding factorial of integers -> 10^14 is possible. I thinks it’s a typo.

9

@only4 why not have a look at https://blog.codechef.com/2009/07/02/tutorial-for-small-factorials .

10

sorry that was a typing mistake.

11

I think you program is same as using 2 variables for finding factorial.

1 Like
12

@only I didn’t mean recursion. I meant:


    ans = 1
    for (int i = 2; i <= n; ++i) 
    {
        ans *= i ;
    }
    return ans

I have removed the if clause. Hope this helps :slight_smile:

If you didn’t understand, feel free to ask me!

13

You could speed up the multiplication by using karatsuba method for multiplication of large numbers.
But multiplication is already assumed to be O(1). So for factorial I don’t think you can do better than O(n) whether you use dynamic programming or not. Using dp you can just avoid recalculation of factorials, but you have to build the factorial table in linear time first. That’s the best you can do. So in 1 sec,

If you want the factorial

20! in C,C++ ; (10^5)! in python

If you want modular factorial

(10^7)! in C C++ python (that’s the best you could do)

14

Thanks I got you.