Rust Tutorial - Dynamic Programming Memoization

This tutorial showcases the speed gains of Dynamic Programming.
The codechef problem.

- mistakes to be amended.
it's not memorization but memoization.(emphasis on memo)

[rumplstiltztinkerstein]

Before saying anything. Let me acknowledge that the video is good. I think it's more important for a video to start a healthy discussion than the code being "perfect".

Because of that I wanted to share an idea.

We could use this technique to calculate fibonacci needing simply an array of 3 values.

Step 1: Initialize the array as [1 1 2].
Step 2: Sum 1 + 2 values and replace the first position [3 1 2]. Return the first.
Step 3: Sum 3 + 2 and replace the second [3 5 2]. Return the second.
Step 4: Sum 3 + 5 and replace the third [3 5 7]. Return the third.
Step 5: Sum 5 + 7 and replace the first [12 5 7]. Return the first.
Step n: Repeat until n.

For this algorithm we can use a counter that increments up to 2 then reset to 0. We won't need to increase array size for higher fibonacci values. And it's related to your topic.

Thanks for the video. I wouldn't have thought of it without the suggestion.

[letsplaychannel]

There is crate offering a macro doing memoization automatically for you. All one has to do is write #[memorize] in front of the function declaration. Crate: memoize

[SkegAudio]

Awesome video! Hope to see more Rust related content :)

[vanov]

New to Rust? You don't need to use "return", just omit your semi colon instead.

[vanya]

wouldn't it make more sense to fill the array with options if you have a function you can't guarantee will always output numbers different from zero?

[kys]

Dude, there's no "r" in memoization...

[fletchcanny]

Pretty sure there's a python macro that can do this, not sure if it exists tho, let alone be possible in Rust. That said your code isn't very idiomatic, while it works I would omit the return statements and semicolons, and only use if blocks as expressions. It's a really good piece of code to use expressions more. Furthermore I would probably create some wrapper function and use a static variable to make it nice to use so that you don't always have to feed in the memo so that it's correct.

[qqqalo]

What's the vscode extension you've got downloaded for help with Rust?

[keineahnung]

Bro at least run it with optimizations

[dorktales]

Nice video, welcome to the Rust Community. Anyway let me drop my two cents here!

fn fibonacci(n: u64) -> u64 {
static mut MEMO: [Option<u64>; 256] = [None; 256];

unsafe { MEMO[n as usize] }
.get_or_insert_with(|| match n {
n if n <= 1 => 1,
n => fibonacci(n - 1) + fibonacci(n - 2),
})
.clone()
}

Use a static variable so you don't have to pass the memo to each call.
Use an array of options so you know if the value at the given location has been calculated, otherwise recalculate it