class Solution {


	/*
	dp[]
	dp[cost.length]
	1201dp[0]0dp[1]0
	2dp[i]dp[i-2]2dp[i-1]
	i-2i-1cost[i-2]cost[i-1]
	dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1])
	O(n)O(n)
	*/
	public int minCostClimbingStairs(int[] cost) {
        int length = cost.length + 1;
        int[] dp = new int[length];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i < length; i++) {
            dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]);
        }
        return dp[length - 1];
    }

		/*
		i2dp[i]dp[i-1]dp[i-2]cost
		 dp0,dp1,dp2O(1)
		*/

		public int minCostClimbingStairs1(int[] cost) {
        int length = cost.length + 1;
        int dp0 = 0;
        int dp1 = 0;
        int dp2 = 0;
        for (int i = 2; i < length; i++) {
            dp2 = Math.min(dp0 + cost[i - 2] , dp1 + cost[i - 1]);
            dp0 = dp1;
            dp1 = dp2;
        }
        return dp2;
    }


	public static void main(String[] args) {

		int[] cost = {10, 15, 20};
		//System.out.println(new Solution().minCostClimbingStairs(cost));

		int[] cost1 = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
		System.out.println(new Solution().minCostClimbingStairs(cost1));

	}


}