leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0746.cpp (700B)

      1 // memorization approach
      2 class Solution {
      3   public:
      4     int minCostClimbingStairs(vector<int> &cost) {
      5         vector<int> vec(cost.size() + 2);
      6         for (int i = 2; i <= cost.size(); i++)
      7             vec[i] = min(vec[i - 1] + cost[i - 1], vec[i - 2] + cost[i - 2]);
      8         return vec[cost.size()];
      9     }
     10 };
     11 
     12 // optimized, memorize only the previous two values
     13 class Solution {
     14   public:
     15     int minCostClimbingStairs(vector<int> &cost) {
     16         int first = cost[0], second = cost[1];
     17         for (int i = 2; i < cost.size(); i++) {
     18             int crnt = cost[i] + min(first, second);
     19             first = second;
     20             second = crnt;
     21         }
     22         return min(first, second);
     23     }
     24 };