From 4689e4e80b479be25f7557d05818f5caa723aafa Mon Sep 17 00:00:00 2001
From: 3gg <3gg@shellblade.net>
Date: Wed, 5 Feb 2025 18:36:31 -0800
Subject: Initial commit.

---
 .../easy/dynamic_programming/01_climbing_stairs.cc | 22 ++++++++++++++++++++++
 1 file changed, 22 insertions(+)
 create mode 100644 top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc

(limited to 'top-interview-questions/easy/dynamic_programming/01_climbing_stairs.cc')

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;
+    }
+};
-- 
cgit v1.2.3