✅ What is the function of the Dictionary here?
public class Solution {
Dictionary<int,int>cached=new Dictionary<int,int>();
public int ClimbStairs(int n) {
if(cached.ContainsKey(n)) {
return cached[n];
}
int output = 1;
if(n<=3){
output = n;
} else {
output = ClimbStairs(n-1) + ClimbStairs(n-2);
}
cached[n]=output;
return output;
}
}
So I wanted to understand the above solution for this LeetCode puzzle https://leetcode.com/problems/climbing-stairs/description/
I am still wondering what the Dictionary is doing here. My guess is that it prevents the code from exceeding the time limit (as my code went to exceed the limit without the Dictionary). But I appreciate any other plausible explanation for the Dictionary's presence here.
Dictionary<int,int>cached=new Dictionary<int,int>();
public int ClimbStairs(int n) {
if(cached.ContainsKey(n)) {
return cached[n];
}
int output = 1;
if(n<=3){
output = n;
} else {
output = ClimbStairs(n-1) + ClimbStairs(n-2);
}
cached[n]=output;
return output;
}
}
So I wanted to understand the above solution for this LeetCode puzzle https://leetcode.com/problems/climbing-stairs/description/
I am still wondering what the Dictionary is doing here. My guess is that it prevents the code from exceeding the time limit (as my code went to exceed the limit without the Dictionary). But I appreciate any other plausible explanation for the Dictionary's presence here.
LeetCode
Can you solve this real interview question? Climbing Stairs - You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps...
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps...
