-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
103 lines (88 loc) · 4.17 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
<html lang="en">
<link rel="stylesheet" href="https://fonts.xz.style/serve/inter.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@exampledev/[email protected]/new.min.css">
<link rel="stylesheet" href="https://newcss.net/theme/night.css">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>JKVargas blog</title>
</head>
<body>
<header>
<h1>Blog about software development</h1>
</header>
<h1>Algorithms</h1>
<ul>
<li>
<h4> Number of ways you can climb the stairs</h4>
<p>Consider a staircase which you need n steps to reach the top. You can climb one or 2 steps each time. How many distinct ways you can climb to the top?</p>
<p>This is the kind of exercise that is not straightforward to write a solution. Consider some stairs that you need to take 4 steps to reach the top.<br>
These are your options to climb it:<br>
1 step, 1 step, 1 step, 1 step<br>
1 step, 1 step, 2 steps <br>
1 step, 2 steps, 1 step,<br>
2 steps, 1 step, 1 step,<br>
2 steps, 2 steps<br>
-----------------<br>
5 ways to climb it.
</p>
<p>Kinda weird to think on a solution for this. Specially when the number go high and you have so many ways to climb it, right? Well, people can use one technique called memoization to solve it. <br>
<a>https://en.wikipedia.org/wiki/Memoization</a><br>The main idea is that you are going to hold the results that you are getting from minor problems in order to not
have to calculate them again. Minor problems because you will need to break as you guessed, the main problem into smaller problems. For example, from the 4th to the 5th step on a n = 5 stairs, you have just one way to climb the stairs.<br>
<br> I am going to use the <a href="https://www.rust-lang.org/">Rust</a> language to describe to you how we can solve this problem.</p>
<pre>
struct Solution;
impl Solution {
pub fn climb_stairs(n: i32) -> i32 {
// this struct is going to help us to hold the results
// for the i'th step.
let mut memo: Vec<i32> = vec![0; n as usize + 1];
Self::check_stairs(0, n, &mut memo)
}
fn check_stairs(i: i32, n: i32, memo: &mut Vec<i32>) -> i32 {
// This will happen when the ith step is beyond
// the size of the stairs
if i > n {
return 0;
}
// If the i'th step is equal to the size of the stairs,
// that means that we reached the top. So that concludes
// one way on how to climb the stairs.
if i == n {
return 1;
}
// Here is the first magic point hehe
// If we have the memo filled for that step then just return
// it, so we don't have to calculate it again :) cool, right?
if memo[i as usize] > 0 {
return memo[i as usize];
}
// Here is the second magic point where the calculation happens.
// Mainly what we are saying here is basically,
// the number of options that we have to climb from the ith step
// to the top is the sum of options for the next step plus the
// number of options for the current step plus 2.
memo[i as usize] = Self::check_stairs(i + 1, n, memo)
+ Self::check_stairs(i + 2, n, memo);
// Here we return the content from our memoization structure
memo[i as usize]
}
}
#[test]
pub fn checks() {
assert_eq!(2, Solution::climb_stairs(2));
assert_eq!(3, Solution::climb_stairs(3));
assert_eq!(5, Solution::climb_stairs(4));
}
</pre>
<p>The complexity for this solution is O(n).<br>
You can try copy/paste it on <a href="https://play.rust-lang.org/">rust playground</a> to test it.</p>
</li>
</ul>
<footer>
<ul>
<li><a href="https://www.linkedin.com/in/jhonny-vargas-69467949/">Linkedin</a></li>
</ul>
</footer>
</body>
</html>