{"id":257,"date":"2020-12-20T02:30:45","date_gmt":"2020-12-20T02:30:45","guid":{"rendered":"https:\/\/www.canosielabs.com\/blog\/?p=257"},"modified":"2020-12-20T18:48:51","modified_gmt":"2020-12-20T18:48:51","slug":"climbing-stairs","status":"publish","type":"post","link":"https:\/\/www.canosielabs.com\/blog\/climbing-stairs\/","title":{"rendered":"Climbing Stairs"},"content":{"rendered":"\n

Today, we’ll talk about the classic climbing stairs problem<\/a>. <\/p>\n\n\n\n

You are climbing a staircase. It takes\u00a0n\u00a0steps to reach the top.<\/strong><\/p>\n\n\n\n

Each time you can either climb\u00a01<\/code>\u00a0or\u00a02<\/code>\u00a0steps. In how many distinct ways can you climb to the top?<\/strong><\/p>\n\n\n\n

How do we compose a solution? First, lets see how this solution can initiatively be solved and then see if it is a dynamic programming problem.<\/p>\n\n\n\n

Initiative Solution<\/h2>\n\n\n\n

Let’s start by looking at some simple cases. We will denote the function f(n) as the distinct number of ways to climb to step n.<\/p>\n\n\n\n

\nf(0) = 1\n
\nf(1) = 1\n
\nf(2) = 2 ([{1, 1}, {2}])\n<\/p>\n\n\n\n

Take a look at f(2) = how many distinct ways can you climb to the 2nd step. We can do this in two ways, by taking 2 1-steps and by taking 1 2-step. Let’s continue. What about f(3)?<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

For f(3), we can see the answer is 3. We can either start with 1-step then take a one additional 2-step, start with a 2-step and take one additional 1-step or simply take three 1-steps. It’s important to note, in order to get to the third step<\/strong>, we must be at step 1<\/strong> (n-2) or step 2<\/strong> (n-1). This indicates that the maximum number of distinct ways to climb to step 3 must include the number of distinct ways to climb to step n-1 and n-2. We’ll see this more clearly with f(4):<\/p>\n\n\n\n

\"\"<\/figure><\/div>\n\n\n\n

We see from the diagram, that f(4) must include f(3) plus f(2).<\/strong> Because the final step from step 3 and step 2 are different, we can conclude that there are no duplicate paths in all of the paths that make up f(2) + the final 2-step AND all the paths that make up f(3) + the final 1-step. <\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Overlapping Sub-problem<\/strong> – Yes. We can see that as we break the problem down, we are repeating the subproblems multiple times. <\/p>\n\n\n\n

Optimal Substructure<\/strong> – Yes. The maximum number of distinct ways to climb to step n is the maximum number of ways to climb to i) climb to step n-1 and take 1 more step plus ii) climb to step n-2 and climb 2 steps. <\/p>\n\n\n\n

Base case(s)<\/strong> – the two base cases for this solution is f(0) = f(1) = 1 since there is only 1 way to be at step 0 (the start) and step 1. <\/p>\n\n\n\n

DP Table<\/h2>\n\n\n\n

For our state, we only need a 1-D array where at each position n, we simply need to store f(n) = the maximum number of distinct ways to climb to step n. <\/p>\n\n\n\n

Memoization<\/h2>\n\n\n\n

\nWe can achieve this solution using a top-down memoization technique. We start at f(n) and keep breaking the problem down into sub-problems until we reach our base cases:<\/p>\n

class Solution {\n    private int[] cache = new int[46];\n        \n    public int climbStairs(int n) {\n        \n        if (n==0 || n==1) {\n            return 1;\n        }\n        \n        if (cache[n]==0){\n            int result = climbStairs(n-1) + climbStairs(n-2);            \n            cache[n] = result;            \n        }            \n        return cache[n];\n    }        \n}<\/code><\/pre>\n
Note: we know from our problem definition, our cache size needs to be 46.  We can be smarter about the size if n was unbounded, but in our case, we want don’t want to add unnecessary complexity.\n<\/p>\n\n\n\n\n
Tabulation<\/h2>\n\n\n\n
\nUsing tabulation, we can compute from the bottom-up.  I.e. Start at f(1), f(2), f(3)…and so on up to f(n).\n<\/p>\n
class Solution {        \n    public int climbStairs(int n) {\n        int[] cache = new int[n + 1];\n        cache[0] = 1;\n        cache[1] = 1;\n        \n        for(int i=2; i<=n; i++){\n            cache[i] = cache[i-1] + cache[i-2];\n        }\n        return cache[n];                \n    }        \n}<\/code><\/pre>

\n<\/p>\n\n\n\n
Conclusion<\/h2>\n\n\n\n
Though the solution is very simple, the tricky portion is the understanding that f(n) = f(n-1) + f(n-2).  While this might be immediately clear to some, it is one of the more common aspects that trick people up.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today, we’ll talk about the classic climbing stairs problem. You are climbing a staircase. It takes\u00a0n\u00a0steps to reach the top. Each time you can either…<\/p>\n","protected":false},"author":3,"featured_media":255,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[11],"tags":[10],"class_list":["post-257","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-coding-questions","tag-coding-questions"],"_links":{"self":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/257","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/comments?post=257"}],"version-history":[{"count":11,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/257\/revisions"}],"predecessor-version":[{"id":276,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/257\/revisions\/276"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media\/255"}],"wp:attachment":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media?parent=257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/categories?post=257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/tags?post=257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}