You are not logged in. Please login at www.codechef.com to post your questions!

×

# Dynamic programming

 0 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) asked 22 Dec '16, 16:34 2★neget 62●8 accept rate: 14% sorry that was a typing mistake. (22 Dec '16, 17:44) neget2★

 2 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. answered 22 Dec '16, 17:20 4★only4 1.5k●2●12 accept rate: 17%
 4 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. answered 22 Dec '16, 17:09 593●3●32 accept rate: 8%
 2 @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. answered 22 Dec '16, 17:27 371●2 accept rate: 23%

And for factorial here's the code

#include <cstring>


# define ll long long

using namespace std;

int result = {0};

ll fact_dp(int n)

{

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


}

answered 22 Dec '16, 17:24 4★only4
1.5k212
accept rate: 17%

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

(22 Dec '16, 17:36)

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

(22 Dec '16, 17:39) 4★
(22 Dec '16, 17:43)
2

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

(22 Dec '16, 17:44)
 0 @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. answered 22 Dec '16, 17:37 4★only4 1.5k●2●12 accept rate: 17%
 0 @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 :) If you didn't understand, feel free to ask me! answered 22 Dec '16, 17:45 371●2 accept rate: 23% Thanks I got you. (23 Dec '16, 07:52) only44★
 0 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) answered 22 Dec '16, 19:10 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,214
×90

question asked: 22 Dec '16, 16:34

question was seen: 1,432 times

last updated: 23 Dec '16, 07:52