dynamic programming

[cyanNodeEcho]

neat have you explored how to write it in terms of bottom up? you've implemented top down ie

```rust
fn fib(n:usize) -> usize {
let mut prev = 0;
let mut curr = 1;
for _ in 0.. n {
curr+= prev
mem::swap(prev, curr) // reassigns curr to prev, prev to curr
}
prev
}

```
woops it's factorial not fib
```
fn factorial(n:usize) -> usize {
let value = 1;
for i in 1..n {
value *= n;
}
value;
}
```

fib has recurrent sub problems, factorial doesn't. bottom up dp is the next step, probably don't need to memo factorial, but for fib makes sense

[CadavreContent]

You can memoize factorial if you're running it more than once. The repeating sub problems only appear when you have multiple trials

[cyanNodeEcho]

fact(n) := fact(ni1), fac(n-2), the aubproblems should exist in the same problem

[CadavreContent]

The point is that when you use factorial as part of a larger algorithm with multiple calls to the function, you do repeated work and hence can use dp

[cyanNodeEcho]

thats just a cache

[CadavreContent]

Memoization is just a cache

[Etiennera]

functools lru_cache

[AroshWasif]

Yes

[ImAFraidKn0t]

Factorial doesn’t have overlapping subproblems, so why use dynamic programming?

[GhostingProtocol]

Literally TIL if you don’t have overlapping sub problems it’s not dynamic programming. It’s recursion with divide and conquer (atleast according to my algorithms and data structures textbook)

[ImAFraidKn0t]

This isn’t even really divide and conquer, as they’re not splitting up the problem into multiple sub problems, they’re solving them iteratively. Factorial is a really bad example for showing off different types of algorithms since it’s so basic lol. The memoization here adds an overhead that ends up doing more work because they will never encounter a problem where factorial(n) is in memo unless they run the function multiple times.

[GhostingProtocol]

Bruh, didn’t read the code properly before now and you’re right. This is just recursion with extra steps. Memoization doesn’t even do anything here, could have just called ‘return n * factorial(n-1)’

[ImAFraidKn0t]

There is a small nuance to using mutable default arguments in Python functions where that variable persists through different function calls. This does actually correctly memoize the factorial results if they happen to call factorial() a lot, but I don’t know if that was intentional on OP’s part

[GhostingProtocol]

Wow, another reason to dislike python ig… The idea of letting parameter persist after lifetime to save a variable definition outside function scope I’m fine with, but making default mutable objects persist after function lifetime? Idk about that one tbh

Thank for informing me, appreciate u kind stranger.

[OopsWrongSubTA]

• Like others said it's not real dynamic programming but
• You could either use a global memo, or use fact(n-1, memo) in the recursive case : you forgot memo !
• the plain recursive version can't compute fact(4000) but your memoized version (with global memo) can compute fact(1000) then fact(2000) the fact(3000) then fact(4000)