Initial commit.HEADmain

1 files changed, 22 insertions, 0 deletions

diff --git a/top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc b/top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc
new file mode 100644
index 0000000..19aa6a1
--- /dev/null
+++ b/top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc
@@ -0,0 +1,22 @@
+class Solution {
+public:
+    int climbStairs(int n) {
+        /*
+        ways(n-1, n) = 1                            -- one step to n
+        ways(n-2, n) = 1 + 1                        -- 1x two-step + 2x one-step
+        ways(  k, n) = ways(k-1, n) + ways(k-2, n)
+        */
+        if (n == 1) return 1;
+        if (n == 2) return 2;
+
+        int ways_n_1 = 1; // ways(n-1, n)
+        int ways_n_2 = 2; // ways(n-2, n)
+        for (int i = n-3; i >= 0; --i) {
+            const int ways_n_3 = ways_n_1 + ways_n_2;
+            // Update
+            ways_n_1 = ways_n_2;
+            ways_n_2 = ways_n_3;
+        }
+        return ways_n_2;
+    }
+};