leetcode

commit beabc2772b11bea2204a9d1006e8d437a2ad9220
parent a4d91e00773b81c6a7f64a9cbea2e1f7eb89754b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 22 Jan 2023 12:46:34 +0100

Dynamic Programming I: Day 2

Diffstat:
M
Problems/0070.cpp
 | 
5
+++++
M
Problems/0746.cpp
 | 
10
+++++++---

2 files changed, 12 insertions(+), 3 deletions(-)
diff --git a/Problems/0070.cpp b/Problems/0070.cpp
@@ -1,3 +1,4 @@
+// memorization approach
 class Solution {
 public:
   int climbStairs(int n) {
@@ -8,7 +9,11 @@ public:
 
     return vec[n];
   }
+}
 
+// optimized, memorize only the previous two values
+class Solution {
+public:
   int climbStairs(int n) {
     int first = 1, second = 1;
     for (int i = 2; i <= n; i++) {
diff --git a/Problems/0746.cpp b/Problems/0746.cpp
@@ -1,3 +1,4 @@
+// memorization approach
 class Solution {
 public:
   int minCostClimbingStairs(vector<int> &cost) {
@@ -6,14 +7,17 @@ public:
       vec[i] = min(vec[i - 1] + cost[i - 1], vec[i - 2] + cost[i - 2]);
     return vec[cost.size()];
   }
+};
 
+// optimized, memorize only the previous two values
+class Solution {
+public:
   int minCostClimbingStairs(vector<int> &cost) {
     int first = cost[0], second = cost[1];
-    if (cost.size() <= 2) return min(first, second);
     for (int i = 2; i < cost.size(); i++) {
-      int cur = cost[i] + min(first, second);
+      int crnt = cost[i] + min(first, second);
       first = second;
-      second = cur;
+      second = crnt;
     }
     return min(first, second);
   }