ā 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.
} 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
Climbing Stairs - 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...
5 Replies
it's a cache. say
n is 6 initially. it would then call ClimbStairs with both 5 and 4 (in that order). the call with 5 does another call with 4 and 3. the result of the call with 4 is stored in the cache. that means the other call with 4 no longer needs to do any calculation, because we've already done it once.
we just access the previously-calculated resultThat's not part of the task here, but I'd probably go as far as adding the number of ways for 1, 2 and 3 steps manually to the dictionary. Then we don't need the if-else
whatever leetcode uses to measure speed and performance is a compelte joke anyway
this is the same solution run twice in a row
alright, thank you for clarifying people š