[DP] Refactor solution to Climbing Stairs

soapyigu · soapyigu · commit b9fc072dc026 · 2019-08-11T22:33:00.000-07:00
diff --git a/DP/ClimbingStairs.swift b/DP/ClimbingStairs.swift
@@ -1,30 +1,28 @@
 /**
  * Question Link: https://leetcode.com/problems/climbing-stairs/
- * Primary idea: Dynamic Programming, use array as a cache to store calculated data
- * Time Complexity: O(n), Space Complexity: O(n)
+ * Primary idea: Dynamic Programming, dp[i] = dp[i - 1] + dp[i - 2]
+ * Time Complexity: O(n), Space Complexity: O(1)
  *
  */
 
 class ClimbingStairs {
-    func climbStairs(n: Int) -> Int {
-        var steps = [Int](count: n + 1, repeatedValue: 0)
-        return _helper(n, &steps)
-    }
-    
-    private func _helper(n: Int, inout _ steps: [Int]) -> Int {
-        // termination case
+    func climbStairs(_ n: Int) -> Int {
         if n < 0 {
             return 0
         }
-        if n == 0 {
+        if n == 0 || n == 1 {
             return 1
         }
         
-        if steps[n] != 0 {
-            return steps[n]
-        }
+        var prev = 0, post = 1, total = 0
         
-        steps[n] = _helper(n - 1, &steps) + _helper(n - 2, &steps)
-        return steps[n]
+        for i in 1...n {
+            total = prev + post
+            
+            prev = post
+            post = total
+        }
+       
+        return total
     }
 }
