Min Cost Climbing Stairs Solutions in C++

// Source : https://leetcode.com/problems/min-cost-climbing-stairs/
// Author : Hao Chen
// Date   : 2019-02-04


class Solution {
    public:
        int minCostClimbingStairs(vector<int>& cost) {
            return minCostClimbingStairs02(cost); 
            return minCostClimbingStairs01(cost); 
        }
        int minCostClimbingStairs01(vector<int>& cost) {
            vector<int> dp(cost.size() , 0);
            dp[0] = cost[0];
            dp[1] = cost[1];
            for (int i=2; i<cost.size(); i++) {
                dp[i] = min( dp[i-1], dp[i-2] ) + cost[i];
            }
            return min(dp[dp.size()-1], dp[dp.size()-2]);
        }

        int minCostClimbingStairs02(vector<int>& cost) {
            int dp1 = cost[0], dp2 = cost[1];
            for (int i=2; i<cost.size(); i++) {
                int dp = min( dp1, dp2 ) + cost[i];
                dp1 = dp2;
                dp2 = dp;
            }
            return min (dp1, dp2);
        }
};

/// Source : https://leetcode.com/problems/min-cost-climbing-stairs/
/// Author : liuyubobobo
/// Time   : 2017-12-16

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

        vector<int> dp(cost.size() + 1, 0);
        for(int i = 2 ; i <= cost.size() ; i ++)
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i - 2]);
        return dp.back();
    }
};


int main() {

    vector<int> vec1 = {10, 15, 20};
    cout << Solution().minCostClimbingStairs(vec1) << endl;

    vector<int> vec2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    cout << Solution().minCostClimbingStairs(vec2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/min-cost-climbing-stairs/
/// Author : liuyubobobo
/// Time   : 2017-12-16

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

        cost.push_back(0);
        vector<int> dp(cost.size(), 0);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2 ; i < cost.size() ; i ++)
            dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
        return dp.back();
    }
};


int main() {

    vector<int> vec1 = {10, 15, 20};
    cout << Solution().minCostClimbingStairs(vec1) << endl;

    vector<int> vec2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    cout << Solution().minCostClimbingStairs(vec2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/min-cost-climbing-stairs/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Space Complexity Optimized
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

        cost.push_back(0);
        int a = cost[0];
        int b = cost[1];
        for(int i = 2 ; i < cost.size() ; i ++){
            int c = min(a, b) + cost[i];
            a = b;
            b = c;
        }
        return b;
    }
};


int main() {

    vector<int> vec1 = {10, 15, 20};
    cout << Solution().minCostClimbingStairs(vec1) << endl;

    vector<int> vec2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    cout << Solution().minCostClimbingStairs(vec2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/min-cost-climbing-stairs/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Little optimizing without changing cost array :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

        int a = cost[0];
        int b = cost[1];
        for(int i = 2 ; i < cost.size() ; i ++){
            int c = min(a, b) + cost[i];
            a = b;
            b = c;
        }
        return min(a, b);
    }
};


int main() {

    vector<int> vec1 = {10, 15, 20};
    cout << Solution().minCostClimbingStairs(vec1) << endl;

    vector<int> vec2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    cout << Solution().minCostClimbingStairs(vec2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/min-cost-climbing-stairs/
/// Author : liuyubobobo
/// Time   : 2018-10-29

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Reverse order to dp :-)
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {

        int a = 0, b = 0;
        for(int i = cost.size() - 1 ; i >= 0 ; i --){
            int c = min(a, b) + cost[i];
            a = b;
            b = c;
        }
        return min(a, b);
    }
};


int main() {

    vector<int> vec1 = {10, 15, 20};
    cout << Solution().minCostClimbingStairs(vec1) << endl;

    vector<int> vec2 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    cout << Solution().minCostClimbingStairs(vec2) << endl;

    return 0;
}