Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find Nth Fibonacci Number using Dynamic Programming (Memoization Approach)
class Solution {
public:
map<int, int> memory; // for storing precomputed answers.
int fibonacci(int n) {
if (memory.find(n) != memory.end()) { // if already exists.
return memory[n]; // just return the precomputed value.
}
// Find the n_th Fibonacci number and make a note of it in memory.
memory[n] = fibonacci(n-1) + fibonacci(n-2);
return memory[n];
}
int n_th_fibonacci(int n) {
memory[1] = 0; // base case that we already know.
memory[2] = 1; // base case that we already know.
return fibonacci(n); // find answer.
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment